No, I didn't sign their Terms until AFTER I had bought and setup my Lumia.
I bought my Lumia partly because it was Advertised with 30GB online storage as a selling bullet point in store (3rd party store but with Microsoft Lumia display advertisement).
That's exactly why we have these consumer laws in the UK, to protect mis-selling via T&Cs.
You may have bought it, but, I don't know in the UK but in Spain there is a 7 or 14 day grace period to exit out of any contract. So you bought the device, received the documentation or read it, and accepted it. If you didn't agree to it, then you could have returned your device to fully cancel the contract. Sadly, I don't think you have a case. Every company puts in their TOC that they have the right to change these terms without even notifying you. Also, we're talking about a free service. When you bought your Lumia, you bought the device and its software; I'd argue (if I were working for MS) that it's a service they extended to you for you to better enjoy your device, not a piece of software that is required by your Lumia to function.
Also, guys, this pisses me off, too! I hate that they're reducing my storage... But once again, we're talking a service that NONE Of us pay for for the camera roll. Microsoft gave it to us with no strings attached. You never had to pay, don't pay, and won't pay for that storage if you don't want it. Yes, it really sucks. I'm sure everyone agrees. It will highly influence my next purchase of a phone seeing how OneDrive offered a lot of space, but couldn't sync as well as other services out there, but nevertheless, it had a lot of space. Now, there are no placeholders, less space, higher megapixels, and for some reason in my area syncing is unnaturally slow! So... Yeah...