Begin edit: By calling FedEx corporate I was able to get them to leave the package at the depot. It really does pay to be polite and respectful even when you are really upset. I love this phone!.
End edit.
This is just great. Fedex, despite delivering dozens of packages to my house over the past 6 months, said they could not find my house. I actually was sitting outside and saw the truck drive around the cul-de-sac and keep going. Both ATT and FedEx verified the correct address but FedEx can't guarantee they can get it delivered today nor can they hold it at the office for me to pickup.
This is crazy.