Since calls used to wind up with the AT&T (or whatever) lady telling us nicely that
"We're sorry, your call cannot be completed as dialed. Please check the number and dial again." and that we could get some outgoing calls to go through and incoming calls work 100% of the time (as tested so far), I decided that the Asterisk server probably wasn't the problem. I asked on the Asterisk forums which are fairly quiet, but still have a couple people who know what they're talking about frequently giving helpful advice. One of them suggested that it was more than likely some sort of timing issue between the Linksys and the phone company.
Thankfully there aren't many relevant timing settings in the Linksys control panel, so I systematically adjusted one of the 4 or 5 that looked to be likely candidates to see what happened (They're all in the Admin -> Voice -> PSTN Line -> FXO Timer Values section). Neither VoIP Answer Delay or PSTN Answer Delay had any effect, which didn't surprise me because we weren't having issues with answering incoming calls (although I guess I've never tried answering an incoming VoIP call from the Linksys). The PIN timeout settings weren't relevant, and "Ring thru" was not something I'd seen mentioned in any of the guides/webpages I had skimmed researching the problem.
The problem seems to have been that PSTN Dialing Delay , previously set to 1, was not long enough. I don't know what kind of "handshaking" goes on behind the scenes when one tries to connect a PSTN call, but based on the terminology I'd guess that previously Asterisk didn't wait long enough to make the proper connection to the PSTN, perhaps truncating or otherwise corrupting the number in the process and leading to the "We're sorry" message. The setting that is working consistently at the moment is:
PSTN Dialing Delay: 2Maybe you can try it on your end to see if things are working in Kansas like they are in Virginia?