Table inside table

You can use the columns environment instead. You can use one column to place the image and another one for the table:

\PassOptionsToPackage{demo}{graphicx}
\documentclass{beamer}

\begin{document}

\begin{frame}
\begin{columns}
\column{.5\textwidth}    
  \centering
  \includegraphics{graph}
\column{.5\textwidth}    
    \begin{tabular}{|p{1cm}|p{1cm}|p{1cm}|p{1cm}|}\hline
        1 & 2 & 3 & 4\\\hline
        4 & 3 & 2 & 1\\\hline
    \end{tabular}
\end{columns}
\end{frame}

\end{document}

The line \PassOptionsToPackage{demo}{graphicx} was only included to make my example compilable for everyone; do not include it in your actual code.

Do not use the center environment inside the table. IIRC it uses a trivlist internally and will add vertical spacing which is normally not wanted in this case. You could use \multicolumn{1}{c}{\includegraphics{graph}} instead.

The tabular inside a tabular or tabular* should be OK. When in doubt just wrap the inner one inside braces { }, but this should normally not be necessary.

The following minimal example works for me. However, centering the graph in such a table with only one row doesn't make sense. The cell is then anyway exactly the size of the graph. Only if there is more than one row it would make sense.

\documentclass{beamer}

\begin{document}

\frame{%
\begin{tabular*}{\textwidth}{l r}
    \multicolumn{1}{c}{\includegraphics{graph}}
    &
    \begin{tabular}{|p{1cm}|p{1cm}|p{1cm}|p{1cm}|}
        1 & 2 & 3 & 4\\\hline
        4 & 3 & 2 & 1\\\hline
    \end{tabular}\\
\end{tabular*}
}

\end{document}