I did a soft reset and tried again (a couple of time) with no luck, unable to send text message.
Went to settings, connections and run through the network provider setup wizard, let it reset the phone and tried again. Settings 'seemed' all the same but SMS now sent without issue.
Will try removing the proxy again later and testing with another SMS.
EDIT: removed the proxy and sent an SMS without issue this time... So was a "completely random coincidence" as rhedgehog said.
Still can't access You Tube via it's mobile client though, at least, it still says no videos...