Chances are it is a problem with your htaccess.
A couple of things about my stuff, falbum 0.6.4, htaccess that comes with wpmu, wpmu from feb 17, 2006. In Falbum options we have fancy urls turned on.
The falbum htacces needs to be near the top ofyour htaccess, in my example below I included the wpmu htaccess above and below the falbum stuff just to give an idea of where i placed it. You should also notice that /wp-inst/ was added into the falbum line, wont work without it, you will also notice that we called our falbum page "gallery" you can call it whatever you want when you set it up.
htaccess looks like...
# Rewrite http://www.domain.com to domain.com
RewriteCond %{HTTP_HOST} ^www.(.*)
RewriteRule ^(.*) http://%1/$1 [R,L]
#Falbum
RewriteRule ^gallery/?([^/]*)?/?([^/]*)?/?([^/]*)?/?([^/]*)?/?([^/]*)?/?([^/]*)?/?([^/]*)?/?([^/]*)?/?$ /wp-inst/wp-content/plugins/falbum/wp/album.php?$1=$2&$3=$4&$5=$6&$7=$8 [QSA,L]
###
#### blogs
###