Actually the act of opening the address in the 'my account' page even if you do not make any changes appears to make the address work.

This is a bit beyond me but I am guessing that when creating a new address during the checkout process it is corrupting the data in the DB. When opening and saving the address in the 'my account' pages it fixes it.

Any help would be appreciated.

Redmonds