Here's an improved third version, using the mdframed package and a definition of a command \mymdtheorem modeled after the original \mdtheorem, but allowing the two colos for the title.
The environment can be used with or without an additional note and on its starred (unnumbered) version:
\documentclass{book}
\usepackage[framemethod=tikz]{mdframed}
\usepackage{lipsum}
\colorlet{titlecolor}{green!20}
\colorlet{numbercolor}{blue!20}
\makeatletter
\DeclareDocumentCommand{\mymdtheorem}{ O{} m o m o }%
{\ifcsdef{#2}%
{\mdf@PackageWarning{Environment #2 already exits\MessageBreak}}%
{%
\IfNoValueTF {#3}%
{%#3 not given -- number relationship
\IfNoValueTF {#5}
{%#3+#5 not given
\@definecounter{#2}%
\expandafter\xdef\csname the#2\endcsname{\@thmcounter{#2}}
\newenvironment{#2}[1][]{%
\refstepcounter{#2}
\ifstrempty{##1}%
{\let\@temptitle\relax}%
{%
\def\@temptitle{\mdf@theoremseparator%
\mdf@theoremspace%
\mdf@theoremtitlefont%
##1}%
}
\begin{mdframed}[#1,frametitle={\strut #4\ \csname the#2\endcsname\@temptitle}]}%
{\end{mdframed}}%
\newenvironment{#2*}[1][]{%
\ifstrempty{##1}{\let\@temptitle\relax}{\def\@temptitle{:\ ##1}}
\begin{mdframed}[#1,frametitle={\strut#4\@temptitle}]}%
{\end{mdframed}}%
}%
{%#5 given -- reset counter
\@definecounter{#2}\@newctr{#2}[#5]%
\expandafter\xdef\csname the#2\endcsname{\@thmcounter{#2}}
\expandafter\xdef\csname the#2\endcsname{%
\expandafter\noexpand\csname the#5\endcsname \@thmcountersep
\@thmcounter{#2}}%
\newenvironment{#2}[1][]{%
\refstepcounter{#2}
\ifstrempty{##1}%
{\let\@temptitle\relax}%
{%
\def\@temptitle{\mdf@theoremseparator%
\mdf@theoremspace%
\mdf@theoremtitlefont%
##1}%
}
\begin{mdframed}[#1,frametitle={\strut%
\begin{tikzpicture}[overlay,baseline=-0.5ex]
\node [fill=titlecolor,anchor=west,inner xsep=10pt,inner ysep=6.5pt,xshift=-10pt] (heading) {#4};
\node at (heading.east) [anchor=west,inner xsep=10pt,inner ysep=6.5pt] {\ \csname the#2\endcsname\@temptitle};
\end{tikzpicture}}]%
}%
{\end{mdframed}}%
\newenvironment{#2*}[1][]{%
\ifstrempty{##1}%
{\let\@temptitle\relax}%
{%
\def\@temptitle{%
\mdf@theoremspace%
\mdf@theoremtitlefont%
##1}%
}
\begin{mdframed}[#1,frametitle={\strut%
\begin{tikzpicture}[overlay,baseline=-0.5ex]
\node [fill=titlecolor,anchor=west,inner xsep=10pt,inner ysep=6.5pt,xshift=-10pt] (heading) {#4};
\node at (heading.east) [anchor=west,inner xsep=10pt,inner ysep=6.5pt] {\@temptitle};
\end{tikzpicture}}]%
}%
{\end{mdframed}}%
}%
}%
{%#3 given -- number relationship
\global\@namedef{the#2}{\@nameuse{the#3}}%
\newenvironment{#2}[1][]{%
\refstepcounter{#3}
\ifstrempty{##1}%
{\let\@temptitle\relax}%
{%
\def\@temptitle{\mdf@theoremseparator%
\mdf@theoremspace%
\mdf@theoremtitlefont%
##1}%
}
\begin{mdframed}[#1,frametitle={\strut%
\begin{tikzpicture}[overlay,baseline=-0.5ex]
\node [fill=titlecolor,anchor=west,inner xsep=10pt,inner ysep=6.5pt,xshift=-10pt] (heading) {#4};
\node at (heading.east) [anchor=west,inner xsep=10pt,inner ysep=6.5pt] {\ \csname the#2\endcsname\@temptitle};
\end{tikzpicture}}]%
}%
{\end{mdframed}}%
\newenvironment{#2*}[1][]{%
\ifstrempty{##1}{\let\@temptitle\relax}{\def\@temptitle{:\ ##1}}
\begin{mdframed}[#1,frametitle={\strut%
\begin{tikzpicture}[overlay,baseline=-0.5ex]
\node [fill=titlecolor,anchor=west,inner xsep=10pt,inner ysep=6.5pt,xshift=-10pt] (heading) {#4};
\node at (heading.east) [anchor=west,inner xsep=10pt,inner ysep=6.5pt] {\@temptitle};
\end{tikzpicture}}]%
}%
{\end{mdframed}}%
}%
}%
}
\makeatother
\mdfdefinestyle{theoremstyle}{%
hidealllines,
frametitlerule=true,%
frametitlebackgroundcolor=numbercolor,
frametitlerulewidth=1pt,
innertopmargin=\topskip,
backgroundcolor=red!20,
splittopskip=1.2\topskip,splitbottomskip=.6\topskip,
}
\mymdtheorem[style=theoremstyle]{example}{Example}[chapter]
\begin{document}
\chapter{Test Chapter}
\begin{example}
\lipsum[2]
\end{example}\par\bigskip
\begin{example*}
\lipsum[2]
\end{example*}\par\bigskip
\begin{example}[A numbered example with a note]
\lipsum[2]
\end{example}\par\bigskip
\begin{example*}[An unnumbered example with a note]
\lipsum[2]
\end{example*}
\end{document}
An image of one of the frames:

And here's an image of the full document obtained (as can be seen, the environment admits page breakings):

Using firstextra, middleextra and secondextra one can produce "closed frames" and a continuation text (as was suggested by azetina in a comment) for the case in which a page break occurs inside the examples:
\documentclass{book}
\usepackage[framemethod=tikz]{mdframed}
\usepackage{lipsum}
\colorlet{titlecolor}{green!20}
\colorlet{numbercolor}{blue!20}
\makeatletter
\DeclareDocumentCommand{\mymdtheorem}{ O{} m o m o }%
{\ifcsdef{#2}%
{\mdf@PackageWarning{Environment #2 already exits\MessageBreak}}%
{%
\IfNoValueTF {#3}%
{%#3 not given -- number relationship
\IfNoValueTF {#5}
{%#3+#5 not given
\@definecounter{#2}%
\expandafter\xdef\csname the#2\endcsname{\@thmcounter{#2}}
\newenvironment{#2}[1][]{%
\refstepcounter{#2}
\ifstrempty{##1}%
{\let\@temptitle\relax}%
{%
\def\@temptitle{\mdf@theoremseparator%
\mdf@theoremspace%
\mdf@theoremtitlefont%
##1}%
}
\begin{mdframed}[#1,frametitle={\strut #4\ \csname the#2\endcsname\@temptitle}]}%
{\end{mdframed}}%
\newenvironment{#2*}[1][]{%
\ifstrempty{##1}{\let\@temptitle\relax}{\def\@temptitle{:\ ##1}}
\begin{mdframed}[#1,frametitle={\strut#4\@temptitle}]}%
{\end{mdframed}}%
}%
{%#5 given -- reset counter
\@definecounter{#2}\@newctr{#2}[#5]%
\expandafter\xdef\csname the#2\endcsname{\@thmcounter{#2}}
\expandafter\xdef\csname the#2\endcsname{%
\expandafter\noexpand\csname the#5\endcsname \@thmcountersep
\@thmcounter{#2}}%
\newenvironment{#2}[1][]{%
\refstepcounter{#2}
\ifstrempty{##1}%
{\let\@temptitle\relax}%
{%
\def\@temptitle{\mdf@theoremseparator%
\mdf@theoremspace%
\mdf@theoremtitlefont%
##1}%
}
\begin{mdframed}[#1,frametitle={\strut%
\begin{tikzpicture}[overlay,baseline=-0.5ex]
\node [fill=titlecolor,anchor=west,inner xsep=10pt,inner ysep=6.5pt,xshift=-10pt] (heading) {#4};
\node at (heading.east) [anchor=west,inner xsep=10pt,inner ysep=6.5pt] {\ \csname the#2\endcsname\@temptitle};
\end{tikzpicture}}]%
}%
{\end{mdframed}}%
\newenvironment{#2*}[1][]{%
\ifstrempty{##1}%
{\let\@temptitle\relax}%
{%
\def\@temptitle{%
\mdf@theoremspace%
\mdf@theoremtitlefont%
##1}%
}
\begin{mdframed}[#1,frametitle={\strut%
\begin{tikzpicture}[overlay,baseline=-0.5ex]
\node [fill=titlecolor,anchor=west,inner xsep=10pt,inner ysep=6.5pt,xshift=-10pt] (heading) {#4};
\node at (heading.east) [anchor=west,inner xsep=10pt,inner ysep=6.5pt] {\@temptitle};
\end{tikzpicture}}]%
}%
{\end{mdframed}}%
}%
}%
{%#3 given -- number relationship
\global\@namedef{the#2}{\@nameuse{the#3}}%
\newenvironment{#2}[1][]{%
\refstepcounter{#3}
\ifstrempty{##1}%
{\let\@temptitle\relax}%
{%
\def\@temptitle{\mdf@theoremseparator%
\mdf@theoremspace%
\mdf@theoremtitlefont%
##1}%
}
\begin{mdframed}[#1,frametitle={\strut%
\begin{tikzpicture}[overlay,baseline=-0.5ex]
\node [fill=titlecolor,anchor=west,inner xsep=10pt,inner ysep=6.5pt,xshift=-10pt] (heading) {#4};
\node at (heading.east) [anchor=west,inner xsep=10pt,inner ysep=6.5pt] {\ \csname the#2\endcsname\@temptitle};
\end{tikzpicture}}]%
}%
{\end{mdframed}}%
\newenvironment{#2*}[1][]{%
\ifstrempty{##1}{\let\@temptitle\relax}{\def\@temptitle{:\ ##1}}
\begin{mdframed}[#1,frametitle={\strut%
\begin{tikzpicture}[overlay,baseline=-0.5ex]
\node [fill=titlecolor,anchor=west,inner xsep=10pt,inner ysep=6.5pt,xshift=-10pt] (heading) {#4};
\node at (heading.east) [anchor=west,inner xsep=10pt,inner ysep=6.5pt] {\@temptitle};
\end{tikzpicture}}]%
}%
{\end{mdframed}}%
}%
}%
}
\makeatother
\mdfdefinestyle{theoremstyle}{%
hidealllines,
frametitlerule=true,%
frametitlebackgroundcolor=numbercolor,
frametitlerulewidth=1pt,
innertopmargin=\topskip,
backgroundcolor=red!20,
splittopskip=1.5\topskip,splitbottomskip=\topskip,
firstextra={%
\draw (P|-O) -- +(-\textwidth,0);
},
middleextra={%
\node[draw,anchor=west,yshift=0.7cm,fill=titlecolor] at (P-|O) {\bfseries Example~\theexample~Continued};
\draw (O-|P) -- +(\textwidth,0);
},
secondextra={%
\node[draw,anchor=west,yshift=0.7cm,fill=titlecolor,inner xsep=8pt] at (P-|O) {\bfseries Example~\theexample~Continued};
\draw (P-|O) -- +(\textwidth,0);
}
}
\mymdtheorem[style=theoremstyle]{example}{Example}[chapter]
\begin{document}
\chapter{Test Chapter}
\begin{example}
\lipsum[1-6]
\end{example}
\end{document}

This continuation text might be redundant since the colored frame indicates a continuation, but I just wanted to illustrate some of the powerful features of mdframed.
mdframedpackage. – Peter Grill Nov 21 '12 at 11:11