How to change the color of \href links... for real

You could add \hypersetup{linkcolor=} in order to remove the coloring of internal links used for navigation purposes:

\documentclass{beamer}
\definecolor{links}{HTML}{2A1B81}
\hypersetup{colorlinks,linkcolor=,urlcolor=links}
\usetheme{Frankfurt}
\begin{document}
\section{Test}
\begin{frame}
  \url{http://tex.stackexchange.com/}\\
  \href{http://tex.stackexchange.com/questions/13423/how-to-color-href-links-in-beamer}{Your question}
\end{frame}
\end{document}

works fine for me as you can see in the headline - the navigation link is colored in the default gray tone, while the links are colored in the desired blue.

If you're looking for something simpler, here's another alternative.

\href{https://www.url.com/}{\color{blue}{\underline{Demo}}}