Update: After my horrid Applecare experience, I went to see a Genius. MUCH better experience. I barely had to explain what was going on before they decided to replace the iPhone, saying, "Since these phones are so new, Apple just wants us to send them back for diagnostics." I don't know if that's a general statement or a coded message saying "Apple knows there's a problem" without admitting it has a problem, but at least they are taking things seriously.
So, I ended up with a new phone. Actually, the first one given to me seemed to have a sensor that was DOA -- it wouldn't even vibrate during the scan process, so the Genius quickly got another one. While it seemed to work fairly well at first, unfortunately again after a day it stopped recognizing any of my scanned fingers.
This makes me feel more assured, along with all the other reports here, that this is a systemic problem with the Touch ID, and not just a few units. To add a bit more experimental rigor to this, I might go in and have the Genius scan in their fingerprint, and then come back a few days later and see if it still recognizes their finger. Though I'm already sure this has nothing to do with bad prints (as it works great right after setting up a print), this would provide some additional data that the unit breaks for two different people.
If this is a hardware problem, Apple is going to have a big problem on its hands with recalls or refunds. But I suspect this is a software problem, and my best guess is still that its "learning" code is corrupting the existing prints with junk data.
The bigger question is, why was this not caught during Apple's supposed extensive testing? Or was it, and they decided they needed a buzzworthy feature for the 5s even though it wasn't 100% solid?