Due to their nested structure, bilevel problems are intrinsically hard to solve - even if all variables are continuous and all parameters of the problem are exactly known. In this paper, we study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we address using the notion of Γ-robustness. We provide an extension of the famous result by Bertsimas and Sim for Γ-robust single-level problems stating that the Γ-robust counterpart of a min-max bilevel problem can be solved by solving a polynomial number of min-max problems of the nominal type. Moreover, we discuss the situation in which the problems of the nominal type are not solved exactly but in which either an α-approximation algorithm or a primal heuristic together with a lower bounding scheme is used. For general Γ-robust bilevel problems, however, we illustrate that the previous ideas cannot be carried over completely. Nevertheless, we present a primal heuristic that is based on the solution of a polynomial number of problems of the nominal type. To assess the performance of the presented methods, we perform a computational study on 560 instances for both settings. For the primal heuristic, we observe that the optimality gap is closed for a significant portion of the considered instances. If our result for the min-max setting is exploited, we report speed-up factors exceeding 400 and 32 in the mean and the median, respectively, when compared to recently published problem-tailored solution approaches.