Choosing between mean, median, and mode as estimator I am testing my estimation procedure on simulated series of a Markov-Switching Vector Autoregression (MS-VAR), meaning a VAR where the parameters switch via an underlying Hidden Markov Chain. 
I simulate data of length $K$, $N$ times from a model where I know the parameters. And then run MLE on each simulated data set.
I am finding the MSE of my estimates is 3% and 1%, when I use the mean & median as the estimator respectively.
Should this cause me concern? When am I theoretically justified in using the median as opposed to the mean?
 A: Yes, you are justified in being concerned.  You are theoretically justified when the mean does not exist, as would be the case in stock market returns, in economic growth in certain cases, or in cancer research.  You would also be justified if the estimator of the mean was less efficient than the estimator of the median for the problem you are facing and you formally solved for efficiency.  It is also reasonably safe when you have no mechanism to determine the likelihood or density function you are working with and you believe robustness is important.  There are circumstances where a mean can be very fragile.
Using the median has a different interpretation from using the mean.  Theories that are based on expectations are having their assumptions violated by using the median in estimation.  You are no longer testing the theory you are claiming to test if an expectation operator is present.  Further, a mean implies a convergence and a direct relationship to the underlying derivative.  The median does not.
For example, if y=5x+2, where the 5 was estimated using ordinary least squares, then it implies that if x=5 then y will converge to 27.  For median regression, such as Theil's regression, it would imply that half the time $y\ge{27}$ and half the time $y\le{27}$.  You cannot make a stronger interpretation than that.
EDIT
From your comment, I can tell you what is wrong.  You are not using the true MLE, you are using a function similar to the MLE.  The median isn't affected by your distributional choice.
The method of maximum likelihood depends strongly upon getting the likelihood function correct.  When you double bounded the possible solutions you changed the constant of integration.  If the constant of integration did not depend upon a parameter, such as $\pi^{-1}$, then truncating the distribution on both sides would only matter if a parameter were brought into the new constant.  However, let's imagine that you were using a normal distribution so the constant of integration includes $\sqrt{\sigma^2}$.  The new distribution will include both $\mu$ and $\sigma^2$ in it and will be a function of the bounds as well.
Since I am assuming you didn't realize this, you are missing the true location of both $\mu$ and $\sigma$ in a systematic manner.  Your higher sample variance implies that the mean and the median are far apart.
You have three choices.  Your first is to use Frequentist methods instead of likelihood methods and use the minimum variance unbiased estimator, which would be the sample mean or OLS.  If that is what you meant by MLE then you should use a median method such as Theil's regression or quantile regression.
The second is to correct the likelihood function and find the true MLE with proper bounding.  The danger involved is that no analytic solution exists and as a result, you cannot form an estimator at all.  This is quite possible as I have never tried it and I would guess that none exists.
The third is to create a Bayesian method with priors with no density outside your range.  The difficulty is that it may be unusually difficult to solve the math for so complex a problem.  You will still need to use a truncated density function, but as you are not taking a derivative, there is no big issue.
I should provide a warning though.  Frequentist solutions can provide impossible answers.  The bounding will be ignored.  It certainly happens from time to time, particularly with truncated distributions.  A second warning is that $\mu$ is no longer a mean, $\sigma^2$ is no longer a variance and $\sigma_{i,j}$ is no longer the covariance between variable $i$ and $j$.  To see why you should consider a distribution with $\mu=.75$ and $\sigma^2=25$ bound between 0 and 1.
Very obviously $\bar{x}\ne{.75}$ and just as obviously $s^2\ne\sigma^2$.
