Finnaly I got it working, thanks to Baruch Even who gave me the code for rewriting the url in lighttpd. If case anyone has the same problems, here it is:
url.rewrite-once = ("^/blog(.*)$" => "/cgi-bin/pyblosxom.cgi/$1")
That's if you have your pyblosxom.cgi in the default space, and want to change "/cgi-bin/pyblosxom.cgi" to "/blog".