\newcommand: Combine (optional) star and optional parameter

With xparse it's very easy to play around with optional arguments and starred variants:

\documentclass{article}
\usepackage{xparse}
\NewDocumentCommand\MyCommand
  {
    s % optional *
    O{1} % first optional argument (default = 1)
  }
  {%
    \IfBooleanTF{#1}
      {The starred variant with parameter: #2}
      {The non-starred variant with parameter: #2}
  }
\begin{document}
\noindent
\MyCommand   \\
\MyCommand*  \\
\MyCommand[2]\\
\MyCommand*[2]
\end{document}

With LaTeX's \newcommand it a little trickier. The \@ifstar macro looks at the next token after the macro is expanded and has absorbed its arguments, so you need to first check for the * and only then look for the optional argument:

\documentclass{article}
\makeatletter
\newcommand\MyCommand
  {%
    \@ifstar
      {\MyCommand@star}
      {\MyCommand@nostar}%
  }
\newcommand\MyCommand@star[1][1]{%
  The starred variant with parameter: #1%
}
\newcommand\MyCommand@nostar[1][1]{%
  The non-starred variant with parameter: #1%
}
\makeatother
\begin{document}
\noindent
\MyCommand   \\
\MyCommand*  \\
\MyCommand[2]\\
\MyCommand*[2]
\end{document}

Both versions print:

Your code works, but not as you expect it to. The \MyCommand[1][1] looks for an optional argument “while expanding” \MyCommand, which then gives you:

\@ifstar{%
  The starred variant with parameter: <optional argument or default>%
}{%
  The non-starred variant with parameter: <optional argument or default>%
}

and only after that the \@ifstar test will be expanded to look for the optional * and choose the text accordingly, so the actual syntax for the command you defined is:

\MyCommand[optional argument]<optional star>

Make \MyCommand take no parameters, but just figure out the star. Then fork from there.

\documentclass{minimal}
\makeatletter
\newcommand\MyCommand{%
  \@ifstar{\mycommandstar}{\mycommandnostar}
}
\newcommand\mycommandstar[1][1]{The starred variant with parameter: #1}
\newcommand\mycommandnostar[1][1]{The non-starred variant with parameter: #1}
\makeatother
\begin{document}
\MyCommand    \\    
\MyCommand*   \\
\MyCommand[2] \\
\MyCommand*[2]
\end{document}