Have you tried to enable “Pretty Permalinks” but the change doesn’t show up on your blog?
I have, and I’ve successfully used this tactic buried in the WordPress Codex’s Using Permalinks article under the “Fixing .htaccess Generation Issues” section.
This only applies if your web host is using Apache (if you aren’t sure, chances are it is, but you might want to check with your host first).
