You know what? Getting an attorney will most likely get you nothing but an attorney's bill. I would send the paper a letter stating who the agreement was with, for how much, and the terms of the contract (rights for use) and simply say that if they violate these terms, then you *will* refer it to an attorney, and please send me a check. Send the letter to the top editor (managing editor, executive editor) and be prepared to talk to him on the phone about it and make nice (compromise.)
Usually, what has happened in these cases, is that some low-level guy who is doing twelve jobs at the same time has overstepped his authority in the name of expediency, and the whole thing has now turned into a pain in everybody's ass. I'd personally write it off as a lesson learned -- you will be taking more photographs, huh? -- and take what money you can get.
If you go screaming off to an attorney, you will probably *never* work again for anybody who hears about it, because people don't want to hear about attorneys. They want people who understand how the system works, and that you either agree to work with it or not. If not, that's usually fine with them, photographers are all over the place. For most newspapers, they could really give a rat's ass whether or not they publish your picture, no matter how good it is. And if you step outside their system, then you've created a lot of problems they just don't have time to deal with.
By the way, I'm not defending what they did -- I'm just saying, that's life when you're dealing with people who have little time for anything but speed. Get used to it or don't do it anymore.
JC