\rowcolor truncating cells in table

Just insert an \hphantom{^{\circ}} like this:

\documentclass{article}
\usepackage[table]{xcolor}

\begin{document}

\begin{tabular}{l|r|r|r}
   Name & Bits & Mean Error  & Max Error   \\
   \hline
   \hline
   A & 15 & $1.45262^{\circ}$ & $3.26743^{\circ}$ \\
   \hline
   \rowcolor{gray}
   B & 16 & $0.37364\hphantom{^{\circ}} $ &  $1.29985\hphantom{^{\circ}}$ \\
   C & 16 & $0.36114\hphantom{^{\circ}}$ & $1.05603\hphantom{^{\circ}}$ \\
\end{tabular}

\end{document}

Another solution, that will save typing lots of \hphantoms and $...$:

\begin{tabular}{l | r | r | r}
   Name & Bits & Mean Error  & Max Error   \\
   \hline
   \hline
   A & 15 & 1.45262\rlap{$^{\circ}$} & 3.26743\rlap{ $^{\circ}$} \\
   \hline
   \rowcolor{gray}
   B & 16 & 0.37364  &   1.29985  \\
   C & 16 & 0.36114  &  1.05603 \\

\end{tabular}