What about running the Apple Hardware test from the CD that came with your MBP? I haven't ever done that, but maybe it would show something about your Airport card?
When you did the full install, did you try it right after the install completed, and then again after the updates were loaded?
Only reason why I'm suggesting that is, that some people seem to have had some issues with certain 10.5.X updates. Maybe the original 10.5.0 install would work?
Just to be extra, extra safe, did you also try the new install at Starbucks?
I can't believe we can't figure this out - unless there is a hardware issue. It's just weird that your computer can see so much about the Airport card, and then still not work...