Ok, I've tried everything I could find. I had no .htaccess file. Yes, I made sure I viewed invisible files on the server. So, I created the file, uploaded it to my server into the WP root folder (the same one that has wp-admin, wp-content, and wp-includes). I then gave it permissions 666 to make sure I could write to it. Went back into WP tried to save custom permalinks, nothing. I've moved the file into wp-admin- didn't work, I moved it back. I've changed the permissions to 777 just to make sure that wasn't it- didn't work either. I even went as far as forcing it to understand it was on an Apache server by using the var.php method of commenting out the Apache line and adding the new one. All of this, and I still error out when I try to go to any other page but the front page using "pretty permalinks" structure.