I was an Espeon around... level 38 or 39, and it took me about three tries to get my Manlady the Moltres. Just be sure to save at the Mid-Point and then if the burning turkey doesn't join you after you lay the smackdown on it, you just restart and only have to trompt around two floors, rather than fourteen or so (an obvious trick, yes, but one can never be sure of what's already know).