Left and right aligned minipages, with table layout

You forgot to use [t] also in the tabular:

\documentclass[letterpaper,12pt]{report}
\usepackage[margin=1in]{geometry}
\begin{document}

\noindent
\begin{minipage}[t]{.49\textwidth}
\raggedright
Some long testing text to illustrate the alignment problem.
\end{minipage}% <-- Don't forget this one
%
\hfill
%
\begin{minipage}[t]{.49\textwidth}
\raggedleft
\begin{tabular}[t]{@{} r l @{}}% <-- Don't forget @{}!
\textbf{Some Long Label} & Bar \\
\textbf{Another Long Label} & Foo Bar Baz \\
\end{tabular}
\end{minipage}

\end{document}

Never use \flushleft and \flushright as commands: they exist only because there are the environments flushleft and flushright. The commands to use are \raggedright and \raggedleft.

An easier approach is with tabular*:

\documentclass[letterpaper,12pt]{report}
\usepackage[margin=1in,showframe]{geometry}
\begin{document}

\noindent
\begin{tabular*}{\textwidth}{@{}p{.45\textwidth}@{\extracolsep{\fill}}r@{}}
\raggedright
Some long testing text to illustrate the alignment problem.
&
\begin{tabular}[t]{@{}r l@{}}
\textbf{Some Long Label} & Bar \\
\textbf{Another Long Label} & Foo Bar Baz \\
\end{tabular}
\end{tabular*}

\end{document}

I added showframe just to show the margins.

Here's a solution that sets each minipage as a tabularx instead:

\documentclass{article}
\usepackage{tabularx}% http://ctan.org/pkg/tabularx
\begin{document}

Some text before.

\noindent
\begin{tabularx}{.5\linewidth}[t]{@{}X@{}}
  Some long testing text to illustrate the alignment problem.
\end{tabularx}%
\begin{tabularx}{.5\linewidth}[t]{%
    >{\raggedleft\bfseries}p{.3\linewidth}
    >{\raggedright\arraybackslash}X@{}}
  Some Long Label & Bar \\
  Another Long Label & Foo Bar Baz
\end{tabularx}%

Some text after.

\end{document}

Alignment of each column is specified using that array package interface (loaded by tabularx).

Note that these blocks will not break across the page boundary.