After some research we discovered the following two things:
- Blogger started using Picasa Web Albums to host the uploaded images - your Google account is tied with Picasa
- This problem seems to be predominantly present in Google managed domains - so if you have mydomain.com and it is being managed by Google Accounts, then you're more likely to stumble across this problem.
I guess that by now most of you are already suspecting something and are probably trying to log on Picasa web albums (http://picasaweb.google.com/) with your google account - you will get an error that the Picasa service is not available on your domain!
Infact it turns out that the problem started when Google accounts were merged at around July and most services were disabled. This is turn, broke the Blogger functionality to utilise Picasa to host the uploaded images.
Therefore to be able to use Picasa with your Google Account, you must enable it by going through your domain dashboard and follow these screenshots:
Now go to Blogger again and you should be able to upload photos!