This seems to be a problem with WordPress’ handling of rewrites and incorrectly sending out 404 headers for pages that exist using other rewrite rules.
I devised a solution detailed on my blog:
http://cyberbrain.prime-artifice.com/2006/03/15/quick-notes-on-modifying-wordpress-20x-permalinks-to-work-with-falbums-friendly-urls/
