My father made the hop from iPhones to the Galaxy S5 recently. He couldn't love the phone more, but also had this same iMessage debacle. It just made him dislike Apple even more, they were awful at resolving the problem, and just left a sour taste in his mouth.

Yeah, I noticed the same. I believe that I fixed it by changing my iCloud password so that my old phone was not authorized to receive iMessages anymore.