Aligning problem

Another option is to use the tabbing environment:

\documentclass{article}
\usepackage[a4paper, left=2.5cm, top=2cm, bottom=2cm]{geometry}

% need this for Croatian letters
\usepackage[cp1250]{inputenc}
\usepackage[T1]{fontenc}

\pagestyle{empty}       % neither header nor footer is shown

\usepackage{sectsty}
\sectionfont{\rmfamily\bfseries\scshape}
\subsectionfont{\rmfamily\mdseries\itshape\large}

\usepackage[bitstream-charter]{mathdesign}
\usepackage[scaled=0.85]{beramono}

% customizing lists
\renewenvironment{itemize}{
    \begin{list}{}{
        \setlength{\leftmargin}{1.5em}
        \setlength{\itemsep}{0.25em}
        \setlength{\parskip}{0pt}
        \setlength{\parsep}{0.25em}
                  }
                          }
                     {
    \end{list}
                         }
% stops paragraphs (section titles) being indented
\setlength\parindent{0em}

\begin{document}
{\huge JOHN DOE}

\vspace{0.5cm}
\begin{minipage}[t]{0.5\textwidth}
Long street 50\\12345 Town\\Country\\
\end{minipage}%
\begin{minipage}[t]{0.5\textwidth}
\begin{tabbing}
Mobile:\ \= +123 45 678 9012 \\
Phone:\> +123 4 5678 901 \\
Email:\> \texttt{[email protected]}
\end{tabbing}
\end{minipage}

\end{document}

Notice that I removed the spurious blank space after the first \end{minipage} to prevent an overfull \hbox.

Use the tabular environment:

\begin{tabular}[t]{l@{ }l}
  Mobile:&+123 45 678 9012\\
  Phone:&+123 4 5678 901\\
  Email:&\texttt{[email protected]}
\end{tabular}

[t] for top alignment of the environment, @{ } for just a bit of space (the default column separation seems too much to me).