I've got some detail on this one as I just encountered it today. This is happening in 4.5.3.
The issue is that for non-admin content editors who have access to more than one workspace, the workspace switcher interface at the top of the page does not actually bring up the clicked workspace unless the Workspaces module is installed. The workspaces that the user has access to are listed, but she cannot switch from one to the other -- the link doesn't do anything beyond closing the drop down menu.
If, on the other hand, you have a user who has access to only one workspace (live or another workspace), that user will be able to access that workspace because no switching is needed. If, for example, I have a workspace called Redesign 2011 and I grant a non-admin editor access to this workspace and not to live, they will be logged in this workspace. If I grant them access to the live workspace as well, they will not be able to switch out of the Redesign 2011 workspace until I also give them access to the workspaces module.
It seems odd that the user has access but cannot switch without have the Workspaces module installed (which in some cases you do not want to do!), so this feels like a bug.
I hope this helps.