did you create a new role totally from scratch? If so, you will see problems like this--even though everything looks to be ok, there are some behind the scenes permissions that do not get set.
What you want to do is copy one of the system roles--select a role such as sales manager, hit actions/copy role--this will create a new role that is an exact copy of the system role, then scale back the permissions as desired. And make sure that they have at least user levelread access to all core entities (account, opportunities, orders, invoices, service calendar, etc), even if they don't use them. If not, you will get errors due to dependancies that aren't obvious.