I have solved the problem. I found that in addition to using the correct permission settings in htaccess you must also add rules to the htaccess file. WordPress attempts to do this automatically, but my server would not allow it.
When you press the button to change the permalink type wordpress creates a new box that has the code you need to copy paste into htaccess. The box is not visible unless you scroll down.