When propagation velocity reduces, electrical length must reduce also to maintain the same resonant frequency, see relation below.
Lambda (wavelength) = (propagation velocity)/frequency
Your antenna behaves like a resonator (likely a quarter wave resonator). When you add loss (via lossy dielectric), the Q factor of the resonator reduces, hence the bandwidth increases. For a resonator:
BW(-3 dB impedance) = Fcenter/Q.
Besides the dielectric loss, there is the radiation loss (very desired in an antenna!). For antennas say < 0.6 lambda, reducing the length of the radiator, reduces the radiation loss. So when using a lossless dielectric the antenna length must decrease (lower propagation velocity), hence the loss reduces, and you get higher Q factor and less bandwidth.
It can be explained with mathematics in a more fundamental and solid way, but this requires at least good understanding of transmission line theory (as almost 90% is transmission line theory).