It's a common problem with iPhones/iPads when you have changed number or carrier.
It is inconsistent and affect some but not all iPhones,
One day Apple will fix this 'glitch' but until then please do the following.
Settings >FaceTime >FaceTime /Off
Settings >Messages >iMessage /Off
Now edit your iPhone to your new number Settings>Phone>My Number
Restart your iPhone
Once you have restarted then please do this:
Settings >FaceTime >FaceTime / On
Settings >Messages >iMessage / On
AS you are both on iPhone 4 can he send an iMessage over 3G with your SIM in his phone?
If so it points, albeit srangely, to a defective SIM
If he cannot then it is the phone's setting that are wrong.
Swapping SIMs will isolate the problem.