The next day, when they sent the shipping confirmation and tracking email, I saw the error. Of course, contacting them was too late; they did ask that I give the post office time to sort it out but were happy to send another one if it was time critical. I opted to wait as the initial mistake was mine, not theirs.
The package arrived a day later than expected, having gone to the small town in the wrong state, been kicked back as "no such address", sent to some big USPS facility in Chicago where they apparently figured out where it should go, manually crossed out the bad city/state/zip and wrote a correct one in and then came straight to me via the local post office, skipping the nearby sorting center that most packages go through.
I don't know how they pulled that one off, especially in a pre-christmas shipping glut, and without the package ever having had the correct address on it until someone working for the postal service figured it out and fixed it. Having a unique name probably helps, as does having a fairly unique street address, but I'm still impressed it didn't just get tossed into the dead-letter pile.
Living in the middle of the country, the post office's abilities are almost magic. Need to send a letter anywhere in the US? Two or three days, for a few cents (no idea what it costs now, I bought a few rolls of "forever" stamps at 40 cents apiece). Need to ship a package? USPS is often cheaper than UPS ground, nearly always cheaper than FedEx ground, and faster than either of them at still only two or three days. Same goes for receiving mail or packages.
Quality of service of all three, I recognize, varies with location and people involved. Around here though, it is damn hard to beat the post office.