I've experienced this. Their device may not be recognized as an Apple iPhone with iMessage.
It may be like when someone has an iPhone with iMessage and they buy a droid and switch to it. They will sometimes not get their messages as some people may still be using iMessage. It was like you had to unregister their device.
Maybe they need to register? If not, take it to the Apple store.
need help. I had to go back to my iPhone 3gs. I can not get ios 5.1.1 to download. it starts then will say it cannot connect after a few minutes. Everything else works fine, my internet works fine. is there another link or a site to download the file?