I am getting error messages when I text. please help.

I am trying to text my friends with my new cell phone number.
after I send it, I immediately get a error message that says. "111-1111 the number is not valid, please enter a 10 digit number or short numner."

k so I changed his contact number to 10 and tried again...

again, I get the same message.... I called ATT. they told me that I had to put the 10 digits or it won't go thru... I told him I already did that. he said to restart my iphone. that was it. I tried calling the apple store,but they were closed.
now I am here asking for your help.
Thanks,
SENSEI