After much searching on the forums and googling I couldn't find an answer, and it even seemed to be a problem affecting users of other packages too (galleries, blogs, etc).
The solution turns out to be a simple one in my case and I thought I'd document it here for other hapless individuals that might come across this:
Turn off MultiViews. It seems when MultiViews is enabled there is confusion between MultiViews and the RewriteRules. So if you go to /user there will be no problem, MultiViews will translate it to /user.php. However when you go to /user/blah/login/blah or one of the other more complex clean URLs it gets confused.
Simply turning off MultiViews solved this with an
Code:
Options -MultiViews





Linear Mode

