Just to update this.
AT&T just provided me with the sim unlock 20 minutes ago... worked
like a charm.
My question is still in to them.. how can others cut thru the bureaucracy to get an unlock when traveling and they have paid the device in full.
I will update again when I get an answer to that question.