There's a couple of ways to solve this problem; unfortunately, I've only got a hack for you at this stage. One problem is that if we redefine the section number "A" to include the word "Appendix", it messes up the formatting of the table of contents. So instead, I've just defined a new sectioning command that prints the section without a number and inserts "Appendix X" manually.
Kind of ugly, but at least it works without having to change any markup :)
\documentclass{article}
\makeatletter
\newcommand\appendix@section[1]{%
\refstepcounter{section}%
\orig@section*{Appendix \@Alph\c@section: #1}%
\addcontentsline{toc}{section}{Appendix \@Alph\c@section: #1}%
}
\let\orig@section\section
\g@addto@macro\appendix{\let\section\appendix@section}
\makeatother
\begin{document}
\tableofcontents
\section{goo}
\label{a}
This is sec~\ref{a}
\section{har}
\label{b}
This is sec~\ref{b}
\appendix
\section{ji}
\label{c}
This is app~\ref{c}
\subsection{me}
does this look right?
\end{document}