As far as backing up her story goes, the passenger was actually with a “bunch of people” in the same carriage with the same issue, it turns out, so it does seem very likely she was told the wrong info by a member of staff at the station as she claims. It was definitely more than one person reporting the same issue.
As far as consumer law goes, the guard is actually not bound to sell the Upgrade (and I agree with you that certainly Virgin appear to advertise it as being available!). You don’t have to sell something at the advertised price. The customer has not paid for the upgrade, so this post on MSE might be helpful:
http://forums.moneysavingexpert.com/showthread.php?t=3277262
Now, if the customer had actually paid for the upgrade, let’s say online or at the station, the guard then has no right whatsoever in claiming it isn’t valid. He cannot chuck her out and he cannot charge her any more money, and if he does then Virgin are in very hot water.
As it stands, I think the best course of action is to contact Trading Standards Scotland about the bad advertising.