Sounds like a permission issue.
Do these users belong to "Project Managers" group?
Do they have "Save Project" permissions?
If you have categories, then explicitly set the "Save project" permissions to them via the PWA.
To do this,
a) Log into PWA (with administrator permissions),
b) Go to Quick Launch menu and choose "Server Settings",
c) Go to Security section, and click on the "Manage Groups"
d) Edit the Project Managers group,
e) Select the category that these users belong to,
f) Set the "Save Project to Project Server" permission to Allow for this,
Save the changes and try now.
I see that you have the latest service pack for your version as well. So should not be something to do with the setup.
I hope this helps.