I contacted Vodafone who said that it was most likely a glitch caused by the new plan starting half way through the month and it would correct itself on next billing cycle.
We have now ticked over to the new cycle, and it's still moving backwards! Logging in to the Vodafone website account shows the same so it's not just a mobile app issue.
I've attached two screenshots from the My Vodafone app. As you can see at 04:12 I had '496MB Left', 11 minutes later (04:22) after watching a couple of videos, I had '517MB Left'.

The observant may note I've used 500MB of my 3000MB plan after only 2 days, I just discovered BaconReader for Reddit. Don't judge!
