What is the upside of treating a factor as random in a mixed model? I have a problem embracing the benefits of labeling a model factor as random for a few reasons. To me it appears like in almost all cases the optimal solution is to treat all of the factors as fixed.
First, the distinction of fixed vs random is quite arbitrary. The standard explanation is that, if one is interested in the particular experimental units per se, then one should use fixed effects, and, if one is interested in the population represented by the experimental units, one should use random effects. This is not of much help because it implies one can alternate between fixed and random views even if the data and experimental design remain the same. Also, this definition promotes an illusion that, if a factor is labeled as random, the inference drawn from the model is somehow more applicable to the population than in case when the factor is labeled as fixed. Finally, Gelman shows that the fixed-random distinction is confusing even at the definition level because there are four more definitions of what fixed and random effects are.
Second, the estimation of mixed models is quite complicated. As opposed to a "purely fixed” model, there are more than a few ways to obtain the p-values. Prof. Bates who implemented REML estimation in the lme4 package in R went so far as to refuse to report the p-values altogether. 
Third,  there is a murky issue of how many implicit parameters are introduced by a random factor. The following example is my adaptation of that in Burnham & Anderson, Model Selection and Multi-Model Inference: A Practical Information-Theoretic Approach. From the bias-variance tradeoff perspective, the role of random effects can be illustrated as follows. Consider a one-way ANOVA with $K$ treatments and $K$ main factor effects, of which $K - 1$ are estimable. The error term has $\mathcal N(0, \sigma^2)$ distribution. If the number of observations is fixed, the bias-variance tradeoff will deteriorate as $K$ goes up. Suppose we say that the $K$ main effects are drawn from $\mathcal N(0, \sigma_K)$ distribution. The corresponding model will have a complexity that is somewhere in between the fixed (overfitted) version and the underfitted model that contains the intercept only. The number of effective parameters in the fixed model is 
$$1 \:\:\mathrm{intercept} + (K - 1) \:\:\mathrm{main\: effects} + 1 \:\:\sigma = K + 1.$$
The number of effective parameters in the random model is at least three: $ \mathrm{intercept}, \sigma, \sigma_K$. In addition,  the random model has  a number of “hidden” parameters implied by the distributional (normal in this case) restriction imposed on the main effects.
In particular, if there is a factor with two levels, it doesn’t make sense to call it random, even if we know for sure that its levels have been sampled at random from some population. That is because the fixed effect version has three parameters, and the random effect version has over three parameters. In this case, the random model turns out to have more complexity than the fixed version. Apparently, a switch from the fixed to random version is more grounded for larger $K$. However, the number of “hidden” parameters in the random model is unknown, so it is impossible to compare the fixed and random versions based on the information criteria such as AIC. Therefore, while this example illuminates the contribution of random effects (the possibility of a better bias-variance tradeoff), it also shows that it is hard to say when it is justifiable to relabel the factor from fixed to random.
None of the above problems are present in a “purely fixed” model. Therefore, I am willing to ask:


*

*Can anyone provide an example when something very bad happened when a random factor was used as if it were fixed? I believe there should be some simulation studies that address the issue explicitly.

*Is there a proven quantitative method to decide when it makes sense to switch from  fixed to random label?
 A: 1. A famous example in psychology and linguistics is described by Herb Clark (1973; following Coleman, 1964): "The language-as-fixed-effect fallacy: A critique of language statistics in psychological research."
Clark is a psycholinguist discussing psychological experiments in which a sample of research subjects make responses to a set of stimulus materials, commonly various words drawn from some corpus. He points out that the standard statistical procedure used in these cases, based on repeated-measures ANOVA, and referred to by Clark as $F_1$, treats participants as a random factor but (perhaps implicitly) treats the stimulus materials (or "language") as fixed. This leads to problems in interpreting the results of hypothesis tests on the experimental condition factor: naturally we want to assume that a positive result tells us something about both the population from which we drew our participant sample as well as the theoretical population from which we drew the language materials. But $F_1$, by treating participants as random and stimuli as fixed, only tells us the about the effect of the condition factor across other similar participants responding to the exact same stimuli. Conducting the $F_1$ analysis when both participants and stimuli are more appropriately viewed as random can lead to Type 1 error rates that substantially exceed the nominal $\alpha$ level--usually .05--with the extent depending on factors such as the number and variability of stimuli and the design of the experiment. In these cases, the more appropriate analysis, at least under the classical ANOVA framework, is to use what are called quasi-$F$ statistics based on ratios of linear combinations of mean squares.
Clark's paper made a splash in psycholinguistics at the time, but failed to make a big dent in the wider psychological literature. (And even within psycholinguistics the advice of Clark became somewhat distorted over the years, as documented by Raaijmakers, Schrijnemakers, & Gremmen, 1999.) But in more recent years the issue has seen something of a revival, due in large part to statistical advances in mixed-effects models, of which the classical mixed model ANOVA can be seen as a special case. Some of these recent papers include Baayen, Davidson, & Bates (2008), Murayama, Sakaki, Yan, & Smith (2014), and (ahem) Judd, Westfall, & Kenny (2012). I'm sure there are some I'm forgetting.
2. Not exactly. There are methods of getting at whether a factor is better included as a random effect or not in the model at all (see e.g., Pinheiro & Bates, 2000, pp. 83-87; however see Barr, Levy, Scheepers, & Tily, 2013). And of course there are classical model comparison techniques for determining if a factor is better included as a fixed effect or not at all (i.e., $F$-tests). But I think that determining whether a factor is better considered as fixed or random is generally best left as a conceptual question, to be answered by considering the design of the study and the nature of the conclusions to be drawn from it.
One of my graduate statistics instructors, Gary McClelland, liked to say that perhaps the fundamental question of statistical inference is: "Compared to what?" Following Gary, I think we can frame the conceptual question that I mentioned above as: What is the reference class of hypothetical experimental results that I want to compare my actual observed results to? Staying in the psycholinguistics context, and considering an experimental design in which we have a sample of Subjects responding to a sample of Words that are classified in one of two Conditions (the particular design discussed at length by Clark, 1973), I will focus on two possibilities:


*

*The set of experiments in which, for each experiment, we draw a new sample of Subjects, a new sample of Words, and a new sample of errors from the generative model. Under this model, Subjects and Words are both random effects.

*The set of experiments in which, for each experiment, we draw a new sample of Subjects, and a new sample of errors, but we always use the same set of Words. Under this model, Subjects are random effects but Words are fixed effects.


To make this totally concrete, below are some plots from (above) 4 sets of hypothetical results from 4 simulated experiments under Model 1; (below) 4 sets of hypothetical results from 4 simulated experiments under Model 2. Each experiment views the results in two ways: (left panels) grouped by Subjects, with the Subject-by-Condition means plotted and tied together for each Subject; (right panels) grouped by Words, with box plots summarizing the distribution of responses for each Word. All experiments involve 10 Subjects responding to 10 Words, and in all experiments the "null hypothesis" of no Condition difference is true in the relevant population.
Subjects and Words both random: 4 simulated experiments

Notice here that in each experiment, the response profiles for the Subjects and Words are totally different. For the Subjects, we sometimes get low overall responders, sometimes high responders, sometimes Subjects that tend to show large Condition differences, and sometimes Subjects that tend to show small Condition difference. Likewise, for the Words, we sometimes get Words that tend to elicit low responses, and sometimes get Words that tend to elicit high responses.
Subjects random, Words fixed: 4 simulated experiments

Notice here that across the 4 simulated experiments, the Subjects look different every time, but the responses profiles for the Words look basically the same, consistent with the assumption that we are reusing the same set of Words for every experiment under this model.
Our choice of whether we think Model 1 (Subjects and Words both random) or Model 2 (Subjects random, Words fixed) provides the appropriate reference class for the experimental results we actually observed can make a big difference to our assessment of whether the Condition manipulation "worked." We expect more chance variation in the data under Model 1 than under Model 2, because there are more "moving parts." So if the conclusions that we wish to draw are more consistent with the assumptions of Model 1, where chance variability is relatively higher, but we analyze our data under the assumptions of Model 2, where chance variability is relatively lower, then our Type 1 error rate for testing the Condition difference is going to be inflated to some (possibly quite large) extent. For more information, see the References below.
References
Baayen, R. H., Davidson, D. J., & Bates, D. M. (2008). Mixed-effects modeling with crossed random effects for subjects and items. Journal of memory and language, 59(4), 390-412. PDF
Barr, D. J., Levy, R., Scheepers, C., & Tily, H. J. (2013). Random effects structure for confirmatory hypothesis testing: Keep it maximal. Journal of Memory and Language, 68(3), 255-278. PDF
Clark, H. H. (1973). The language-as-fixed-effect fallacy: A critique of language statistics in psychological research. Journal of verbal learning and verbal behavior, 12(4), 335-359. PDF
Coleman, E. B. (1964). Generalizing to a language population. Psychological Reports, 14(1), 219-226.
Judd, C. M., Westfall, J., & Kenny, D. A. (2012). Treating stimuli as a random factor in social psychology: a new and comprehensive solution to a pervasive but largely ignored problem. Journal of personality and social psychology, 103(1), 54. PDF
Murayama, K., Sakaki, M., Yan, V. X., & Smith, G. M. (2014). Type I Error Inflation in the Traditional By-Participant Analysis to Metamemory Accuracy: A Generalized Mixed-Effects Model Perspective. Journal of Experimental Psychology: Learning, Memory, and Cognition. PDF
Pinheiro, J. C., & Bates, D. M. (2000). Mixed-effects models in S and S-PLUS. Springer.
Raaijmakers, J. G., Schrijnemakers, J., & Gremmen, F. (1999). How to deal with “the language-as-fixed-effect fallacy”: Common misconceptions and alternative solutions. Journal of Memory and Language, 41(3), 416-426. PDF
A: Suppose I have a manufacturing process that involves making material on several different machines.  They're the only machines I have so "machine" is a fixed effect.  But I make many lots of material on each machine and I am interested in predicting things about future lots.  I'll make "Lot number" a random factor because I'm interested in the results that I'll get for future lots.
A: So you treat them as random so that there is an averaging effect between the overall average and the average for that particular factor based on the sample size of the factor and the overall number of observations. This allows you to say that your results apply to the population at large, since you have a type of weighted average and an estimate of the variation due to that factor, if not, you really can only say that your results apply to the factor levels you used since the regression will treat them as discrete factors and not random ones that get the weighted averaging.
They are also useful when you have repeated measures on the same subject, since you can use them to account for the correlation between measures on the same subject.
A: When we have a grouping structure to our data $ Y_{ij} = \beta_1 X_{ij} + \beta_2 Z_{i} + e_{i} + \mu_{ij}$ where $X_{ij}$ are the observables of our individual observations and $Z_{i}$ are observations invariant among them and only observed at the grouping level, we cannot use fixed effects if we want to estimate $\beta_2$, since if we use the within estimator, $Z_{i}$ drops out, and if we use dummy variables for each $i$, $Z_{i}$ is collinear with them. So if we use a fixed effects estimator in this situation, we are ignoring potentially important information.
Even in the case $ Y_{ij} = \beta_1 X_{ij} + e_{i} + \mu_{ij}$ where we do not have any $Z_{i}$, we may still want to use random effects for a few reasons, despite the problems that may come with them, some of which are listed in your question. 
In these kind of settings, random variation has two (or more if there are multiple grouping levels) sources of variation - variation "within" a group and variation "between" groups. The fixed effects (or "within") estimator completely removes variation between groups in estimating $\beta_1$. The random/mixed effects estimator allows "between" variation to contribute to the estimate of $\beta_1$, theoretically resulting in smaller standard errors. 

(Original Answer)
One place where you are essentially required to use random effects is when you want to include parameters that are invariant at the grouping level of the fixed effect.
For example, say you want to investigate the impact of doctor characteristics (eg/ education) on patient outcomes. The dataset is patient-level with observed patient outcomes and patient /doctor characteristics. Since patients treated under a single doctor are likely correlated, you want to control for this. You could insert a doctor fixed effect here but in doing so, you preclude including any of the doctor characteristics in the model. Which is problematic if the interest is in doctor-level characteristics.
A: I think it's related to consistency of the estimates.
Let's say $x_{ij} = a_i+b_j+e$ where $a_i$ stands for fixed effect(some experimental condition)
and $b_j$ stands for random effect(may person).
Neyman and Scott(1948) points out the problem of consistency of
Maximum Likelihood Estimates of $a_i$ and $b_j$.
If we take $a_i$ and $b_j$ as both fixed effect, the estimates are no longer
consistent. At least, that's how I understood...
