Permalink 4004 error

I recently installed wordpress 2.3 and I am having trouble with my permalinks. I changed them to /%category%/$post_id%/ and since doing that all my link gave me a 404 error. I placed my .htaccess in the same place as my index.php file and I have the .htaccess set to 777 so it can be written on. I have completed erased everything off my server and started over from scratch and nothing… I had gotten it to work once before but nothing recently. What else is there to do? I read the codex and have done tons of searches but I can’t seem to solve my problem.