Having major issue with phone number formatting

I just got my first iPhone today and I'm having a major problem with number formatting that I have never had before on even basic cell phones.

On my iPod Touch, I used to type in 10 digits in a phone number field and the iPod automatically formatted it, for example it would make it (123) 456-7890. Today, when everything transferred over to my new phone, the format of these numbers was 1234567890. Okay I thought, as long as it works. Here's my problem though. When I text someone whose contact info has this format, the phone correctly shows the persons name. However when I call them or miss a call, and go to my recent calls list, it doesn't show the persons name, it shows their number.

Okay so then I changed the format to +1 (123) 456-7890 AND 11234567890, which seem like the only other two ways to do it. Both of these had the same problem. They fixed the recent calls list problem, which now correctly shows the persons name. But it introduced a new problem. I texted someone using this number format and the text went through. When They replied however, the reply went to its own new messaging thread, with the format 1234567890 and without the persons name.

So I don't know what to do. Each format let's me have one thing right and one thing wrong. The only solution I can think of is to put two numbers for each person, one using each format, but that's stupid. I must be missing something here, please tell me that I am. Thank you!

In case you're wondering I'm on an iPhone 4S with iOS 5.

 

Sorry to bump my own thread but I really needed some help here, it's bothering me like crazy.

 

It's seems so weird though. Try creating a contact right now on your iPhone and type digits 0-9. How does your phone format it? 0123456789 or (012) 345-6789? Mine does the first one.