Paste was easy to understand once I realized what WSGI enables. (Ben Bangert's Google Tech Talk gives a pretty nice explanation on WSGI.)
The only real problem I see is that most Python web developers don't know that they can ask the questions that Paste is the answer to.
Also, while I don't know whether this WSGI middleware business is exactly "rocket science", I do think that a lot of programmers don't really care about the stuff WSGI and Paste (etc) solve. They should care, of course, but they don't. (PHP is the ultimate proof of this. Not to say that PHP is inherently evil, though.)