In General settings> International> Region Format= United States?
If No fix: Go to each contact>Edit>tap on the # and see if it can backspace once to fix.(if you try and add just one extra # it does that//11#'s)If not fixed then, try adding "+1" in front of number.
And i seen this has helped a few on MR.//Open the multitasking bar by double clicking the home button (it will slide up from the bottom). Then hold in the phone icon for about three seconds until it starts to jiggle. Then click the X in the upper right corner. Click the home button to return back to normal.
BTW: I have not tested this to see if it fixes, only read it.. but it did no harm on mine trying.