I'm sure you read http://codex.wordpress.org/Using_Permalinks
And read the following:
Using only %postname%
If you use postname as the only element in your permalinks to create a structure such as example.com/post-title, the rewrite rules may make it impossible to access pages such as your stylesheet (which has a similar format) or the /wp-admin/ folder [is this true in WordPress 2.0+ versions?]. It's best to include some numeric data (e.g. the post ID or date) in the permalink to prevent this from happening. Additionally, WordPress v1.2.x requires the use of a date structure in order for some features, such as the calendar, to function properly. /%year%/%monthnum%/%day%/%postname%/ is always a good start.
For the rest there could be a couple of reasons for your error. Can you use mod/rewrite and htaccess? Having a look at file permissions could be an idea. Best just start with trying if one of the default pretty permalinks does work (that would answer my two questions) and if that does, follow my advise and make at least id/postname.