Posted too soon!

They log into SSMS as DomainName\Username yes? If you check under Security > Logins > DomainName\Username right-click, Properties, what have they got under Server Roles? And what have they got under User Mapping (i.e. are there any databases they're mapped to?)