Band structure calculations for photonic crystals require the numerical solution of eigenvalue problems. In this paper, we consider crystals composed of lossy materials with frequency-dependent permittivities. Often, these frequency dependencies are modeled by rational functions, such as the Lorentz model, in which case the eigenvalue problems are rational in the eigenvalue parameter. After spatial discretization using an interior penalty discontinuous Galerkin method, we employ a recently developed linearization technique to deal with the resulting rational matrix eigenvalue problems. In particular, the efficient implementation of Krylov subspace methods for solving the linearized eigenvalue problems is investigated in detail. Numerical experiments demonstrate that our new approach is considerably cheaper in terms of memory and computing time requirements compared with the naive approach of turning the rational eigenvalue problem into a polynomial eigenvalue problem and applying standard linearization techniques.