I had a very similar error recently, that only came to light following an upgrade from Tridion 2013 GA to SP1.
The message that I was seeing was:
HTTP 400 - Bad Request (Request header too long)
The problem was that the one user in question was a member of a large number of Active Directory Groups. The solution to this was to increase the MaxFieldLength and the MaxRequestBytes registry keys on the IIS server, as described in the following Microsoft KB articles:
Although not exactly the same error that you are seeing, some sources seem to suggest that the cause of your 'Invalid verb' issue could include:
Improperly demarcated requests in the HTTP stream altered what the
server interprets as the "verb"
and that this may be caused
If the users have heavy Domain Group membership which come up with
complicated Kerberos tokens
If the issue is related to the Domain Groups that your user is listed in, then this would explain why the same issue is not being encountered by your colleague.
You may want to look in to the two KB articles listed above.
Alternatively, if you are using IIS6, then you may want to look in to the following Microsoft hotfix (again, related to the Domain Groups that a user in a member of): Http.sys rejects requests that contain separator characters