It's been a long while but, especially as a young employee (presumably) expecting to have relocation handled, I'd be WTF; the relocation would probably have been a huge chunk of my salary at the time. Of course, at that point, you're probably just screwed and you're probably not going to get a lawyer over it.
Have they not formed a verbal contract in saying they'll help with relocation expenses?