I have found the same frustration when dealing with hiring sysadmins/netadmins/DBAs -- the seminal difference with those is that while your "senior programmer"'s ineptitude should be shaken out in QA, your "senior sysadmins" incompetence might get found out the first time he/she's on an overnight call by himself and brings down your production system(s).
I, too, have changed the way I do interviews: I always do a phone screen second. First, I make sure that people pass what I call my "0th order clown filter" -- that is, I make sure that those I solicit can actually read and follow simple directions. (Obviously, this doesn't apply when dealing with recruiters, the number of whom with a clue is a set of measure 0.)
I have also developed a pretty standard list of graded questions that allow me to quickly determine if letting someone loose on a production system/database/network is safe or highly ill-advised. (These are also questions that aren't easily discoverable via Google/Bing/Wolfram Alpha.) The downside to a standard set of questions is that if you deal with recruiters, the questions very quickly get passed back up and subsequent candidates from the same recruiter get prepared.
Other commenters' notes about "problem solving vs. programming" are well-taken, but if, coming in, your candidate can't show that he's got a reasonable-sized toolbox of problem solving already, you're going to spend a lot of time teaching him or her, rather than getting him or her to do the work -- which can be costly in the case of a "senior whatever".