It may well be that the short-term fix I put in at #7097 is not yet good enough. [It is short-term since the latest version of pari have fixed some bugs which arose for non-monic polynomials, which is why the patch I put in at #7097 made sure that pari was only called to factor monic ones.]

I just had a possibly worse example, and found this ticket while looking to see if I should open a new one:

sage: E = EllipticCurve('4900a2')
sage: f = E.division_polynomial(9)
sage: K3.<z> = CyclotomicField(3)
sage: ff = f.change_ring(K3)
sage: ff.degree()
40
sage: [g.degree() for g,e in ff.factor()]
[1, 3, 9, 40]

I factor a degree 40 polynomial and the returned factors have degrees 1,3,9,40!
Even if I make the polynomial monic (above it has leading coefficient 9) it is no better:

sage: x = f.parent().gen()
sage: g = 9^39 * f(x/9)
sage: all([c.is_integral() for c in g.coefficients()])
True
sage: [h.degree() for h,e in g.change_ring(K3).factor()]
[1, 3, 9, 40]