I'd like to add to this thread if I may. I tried my first MultiSite installation today, WP 3.0.4 on a XAMPP localhost (Windows) with both MySQL and PHP a current 5.x version. I used a sub-folder installation and created a second test blog. No plugins, unmodified TwentyTen theme. Everything works fine, except the permalinks for static pages in the default blog. From what I can see at the OP's website, it looks like it's the same problem.
@asafche: mod_rewrite works at least partly, as you can see on pages like these: http://www.moob.me/blog/category/uncategorized/
@andrea_r and everyone else: Regardless if .htaccess works or doesn't work -- shouldn't WP generate links for static pages as "/blog/hello-world" instead of "/hello-world"? Every other permalink on the default blog has the "/blog/" prefix, just not the static pages. My permalink structure by the way is "/year/month/title".
Ok, there is one difference to asafche: In my case, I can see the static pages. They are displayed just fine, and when I try to create a new static page with the name of an existing blog, it gets a weird permalink with an appended "10" (e.g. "/techblog10"). So this might be two unrelated problems for the OP: WP generates the wrong permalinks (a bug?) and then the wrong permalinks don't work.
Is there anything I can do to help clear this up? As my installation is on my local machine, I can try out pretty much anything that could help. :-)