I've just been contacted by Vodafone via the phone.

They say that they cannot cancel my contract yet, until I can prove that the new charges directly affect me, even though all they have to do is look at my previous usage. Every month since I started my contract, i've been way over the 500mb limit.

Apparently all I have to do is wait for my next bill to come through, with the extra charges, then call them, and they will "review my contract".

Success!