Phone adds number prefix when replying to sms

I have all phone numbers for my contacts saved in international format, ie +4670xxxxxxx, since 46 is the country prefix for Sweden, where I live.
When I reply to an sms from someone in my contact list, the phone apparently adds an extra "46", so it tries to send the message to +464670xxxxxxx, and then I immediately get a "could not send message" reply from my operator.
Why does this happen? I checked more than twice, I have not entered the wrong number in the contact.