@Cndnmax, Thank you for your suggestion, things didn't exactly go the way you had described, but what finally got it through was that I insisting on talking to the technical support.
To start I just want to say, ATT is very very confused, and my best suggestion is to keep on calling and don't believe in what anybody said until you got it resolved. Of course, this only applies to people who asked for the unlock early enough and is still waiting. At least that was the basis of my argument. Note, my is an iPhone 2G so I'm 100% certainly is out of contract, no argument there.
I submitted my request on the 9th of April. First was giving a 72 hours wait, that was no good, then was giving a 16th deadline that was no good either. I finally called back again this morning, first I got to the CS, then I asked for the CS manager he was extremely rude and extremely protective of his CS personal and insisting on there is nothing more he (or ATT) can do and I'm just wasting my time (Note. I was extremely clam and logical until the CS manager became very rude. He was rude the entire time). Also, just before transferring to tech support, he said "I'll transfer you there, but there is NOTHING they can do, it's all in Apple's court". I told him to transfer me anyways.
When I got the tech support, I calmly explained my case again and was told the long wait time is most likely due to high unlock request. I told the tech that I do not disagree with your statement, however, I made the request on the 9th of April and I would think that I'm somewhat ahead of most people in the line, unless this is not first come first serve situation. The tech agreed with me (she was very nice the entire time), and ask me to wait a few second to verify the phone, and of course this is a iPhone 2G so it's long been free of contract. Much to my surprise the tech then said, okay, I will unlocked it for you. Which I thought that WAS not possible by the very rude CS manger who flat out lied to my face about the fact it's Apple's problem. Anyways, long story short, the iPhone 2G is now unlocked after a restore. I plan to use this as my backup phone or should I need to travel over seas.
Conclusion:
1. Most CS at ATT has no idea what is going on, some will blame ATT some will simply blame Apple, maybe just because it makes more sense. The rude CS manager kept on telling me "ATT don't make the phone, Apple does" I think he said it at least give times during the conversation. I guess when you are lying you gotta do it with confidence.
2. From the looks of it tech support does have the ability to unlock your phone if you are certain that your phone is out of contract and have waited long enough (I waited 9 days). Which was the basis of my argument.