Permalinks problem with custom theme

Sounds like you …

  1. Don’t have mod_rewrite installed or enabled
  2. Or your .htaccess file in not being edited

To check the first make a file with <?php phpinfo(); in it, save it to your server– same place you have WordPress– named something like phpinfo.php, and load the file in a browser. Look for mod_rewrite. It should be near the top in the “Loaded Modules” rows. If it isn’t there, the only setting that will work is the default. Unless you can install that module or talk your host into installing it.

As for the second, WordPress should give you message if it can’t create/write the .htaccess file. When you save the permalinks look for that message. If you see it you will need to copy and paste the .htaccess rules into the file by hand or alter the permissions on the server to so that WordPress can write the file.

Reference

http://codex.wordpress.org/Using_Permalinks