When is it okay to look for another job?

I can't figure out if these things are brilliant or silly
Photo credit: mytorontomovingandstorage

Consider the following scenario:

• A chemist is hired for a position at a company in a city that is of moderate desirability. The company offers a relocation package; the candidate takes the package. 
• Soon after their arrival and start date, they see a better position in a far more desirable city (closer to family, etc.). 

What is the appropriate thing to do? Is it okay to look? Is it okay to apply? You're probably going to have to pay all or most of your relocation package (is it me, or do these things have a 2 year repayment period these days?) 

I think that it's much more about 'hard feelings' than anything else; if a company picks you and you reject them (after they've invested a fair bit in you), you're probably burning your bridges. That being said, if it's your dream job and a dream city, etc., it may be worth it. 

Readers, what say you? What's the shortest amount of time that you have to stay at a chemistry position before it's terribly gauche to move on?*

*There's a "When Harry Met Sally" joke in here somewhere.