In case this helps someone with the same problem, I have the solution :
I had to check the Settings - Wireless and network - Mobile network - Use packet data check box. When this was done, I could send picture MMS messages.
Maybe obvious for some .. but it sure was one setting I thought I should not need just to send an MMS message.