Please VOTE for your favorite Christmas Project selection.
I doubt, though it's possible, that this is a hardware issue.
Whenever there's an issue with requiring area codes(or in your case country code!), it's usually a carrier-side issue. Sounds like you're already working on contacting the carrier.
I previously had an issue after moving to a new town where the phone wouldn't choose the closest cell tower and kept trying to utilize the further one whenever a call was made or received which resulted in many dropped calls. The staff at Verizon were stumped. After attempting all the software-side fixes, I did a factory reset of the phone and it suddenly worked.
And they call these phones "smart".
For me, I default enter the #1 before all my contacts because we have so many area codes locally, it just became a habit, even if they are in my area code. I've never had an issue? Usually around here it gets mad at me if I don't have the #1.
World's Okayest Fiddler