If I understood your question correctly, here's a possible solution; I added a colored framed around the section titles in the both the general ToC and in the ToCs generated at the beginning of each section:
\documentclass{beamer}
\usepackage{tikz}
\usetheme{Malmoe}
\newcommand\sectioncolor{white}
\newcommand\SectionBox[1]{%
\tikz\node[rectangle,fill=\sectioncolor,rounded corners] {#1};
}
\AtBeginSection{%
\setbeamercolor{section in toc}{fg=black,bg=\sectioncolor}
\begin{frame}<beamer>
\frametitle{Outline \thesection}
\tableofcontents[currentsection,subsectionstyle=show/show/shaded]
\end{frame}
}
\setbeamertemplate{section in toc shaded}[default][7]
\makeatletter
\long\def\beamer@section[#1]#2{%
\beamer@savemode%
\mode<all>%
\ifbeamer@inlecture
\refstepcounter{section}%
\renewcommand\sectioncolor{%
\ifcase\value{section}\or blue!20\or green!80!black\or red!80!black!50\or yellow!30!black!50\else orange!30!black!50\fi}
\beamer@ifempty{#2}%
{\long\def\secname{#1}\long\def\lastsection{#1}}%
{\global\advance\beamer@tocsectionnumber by 1\relax%
\long\def\secname{#2}%
\long\def\lastsection{#1}%
\addtocontents{toc}{\protect\beamer@sectionintoc{\the\c@section}%
{\protect\tikz\protect\node[rectangle,fill=\sectioncolor,rounded corners] {#2};}%
{\the\c@page}{\the\c@part}%
{\the\beamer@tocsectionnumber}}}%
{\let\\=\relax\xdef\sectionlink{{Navigation\the\c@page}{\noexpand\secname}}}%
\beamer@tempcount=\c@page\advance\beamer@tempcount by -1%
\beamer@ifempty{#1}{}{%
\addtocontents{nav}{\protect\headcommand{\protect\sectionentry{\the\c@section}{#1}{\the\c@page}{\secname}{\the\c@part}}}%
\addtocontents{nav}{\protect\headcommand{\protect\beamer@sectionpages{\the\beamer@sectionstartpage}{\the\beamer@tempcount}}}%
\addtocontents{nav}{\protect\headcommand{\protect\beamer@subsectionpages{\the\beamer@subsectionstartpage}{\the\beamer@tempcount}}}%
}%
\beamer@sectionstartpage=\c@page%
\beamer@subsectionstartpage=\c@page%
\def\insertsection{\expandafter\hyperlink\sectionlink}%
\def\insertsubsection{}%
\def\insertsubsubsection{}%
\def\insertsectionhead{\hyperlink{Navigation\the\c@page}{#1}}%
\def\insertsubsectionhead{}%
\def\insertsubsubsectionhead{}%
\def\lastsubsection{}%
\Hy@writebookmark{\the\c@section}{\secname}{Outline\the\c@part.\the\c@section}{2}{toc}%
\hyper@anchorstart{Outline\the\c@part.\the\c@section}\hyper@anchorend%
\beamer@ifempty{#2}{\beamer@atbeginsections}{\beamer@atbeginsection}%
\fi%
\beamer@resumemode}%
\makeatother
\begin{document}
\begin{frame}
\frametitle{General Outline}
\tableofcontents
\end{frame}
\section{Test Section One}
\subsection{Test Subsection One One}
\begin{frame}test one\end{frame}
\subsection{Test Subsection One Two}
\begin{frame}test one\end{frame}
\section{Test Section Two}
\subsection{Test Subsection Two One}
\begin{frame}test one\end{frame}
\subsection{Test Subsection Two Two}
\begin{frame}test one\end{frame}
\subsection{Test Subsection Two Three}
\begin{frame}test one\end{frame}
\section{Test Section Three}
\subsection{Test Subsection Three One}
\begin{frame}test one\end{frame}
\subsection{Test Subsection Three Two}
\begin{frame}test one\end{frame}
\end{document}
The general ToC:

Two of the ToCs at the beginning of sections:


Since the modification is required for the sections in the navigation bar and not in the ToCs as I initially thought, the solution is much easier: all that is requierd is to redefine the templates section in head/foot (for the current section) and section in head/foot shaded (for sections different from the current one). In the following example I used a colored frame for the current section, but you can use any other style you like:
\documentclass{beamer}
\usepackage{tikz}
\usetheme{Singapore}
\definecolor{SectionBox}{RGB}{60,160,0}
\setbeamertemplate{section in head/foot}{\hfill\protect\tikz\protect\node[rectangle,fill=SectionBox!90,rounded corners=1pt,inner sep=1pt,] {\textcolor{white}{\insertsectionhead}};}
\setbeamertemplate{section in head/foot shaded}{\textcolor{structure!40}{\hfill\insertsectionhead}}
\begin{document}
\section{Test Section One}
\subsection{Test Subsection One One}
\begin{frame}test section one\end{frame}
\subsection{Test Subsection One Two}
\begin{frame}test section one\end{frame}
\section{Test Section Two}
\subsection{Test Subsection Two One}
\begin{frame}test section two\end{frame}
\subsection{Test Subsection Two Two}
\begin{frame}test section two\end{frame}
\subsection{Test Subsection Two Three}
\begin{frame}test section two\end{frame}
\section{Test Section Three}
\subsection{Test Subsection Three One}
\begin{frame}test section three\end{frame}
\subsection{Test Subsection Three Two}
\begin{frame}test section three\end{frame}
\end{document}
Some images of some of the headlines:


