/%year%/%monthnum%/%postname%/ works for me. I think any non-numeric structure that includes %postname% will work.

That helped, definitely need to include %postname%.

I am on Snow Leopard running a basic install of apache. For each folder in my /Sites/ folder where I am running wordpress I need to add this .htaccess file:

    # Exclude the file upload and WP CRON scripts from authentication
    <FilesMatch "(async-upload\.php|wp-cron\.php|xmlrpc\.php)$">
        Satisfy Any
        Order allow,deny
        Allow from all
        Deny from none
    </FilesMatch>
    # BEGIN WordPress
    <IfModule mod_rewrite.c>
    RewriteEngine On
    RewriteBase /wordpress/
    RewriteRule ^index\.php$ - [L]
    RewriteCond %{REQUEST_FILENAME} !-f
    RewriteCond %{REQUEST_FILENAME} !-d
    RewriteRule . /wordpress/index.php [L]
    </IfModule>

# END WordPress

replace /wordpress/ with the name of your wordpress installation.

You should only need that .htaccess file in your root. If you are running on a local dev machine, you only need to have an .htaccess in your web root. On a public site, you should have one per directory, but only to restrict browsing of those directories by unauthorized users.

I'm currently having '/notes/%post_id%' structure, and everything works fine. AFAIK all you need is just to setup permalinks once with any structure, everything worked fine for me after i've finished the installation - maybe the problem is somewhere else.