First of all, the obvious answer: do you have the Security set in the admin console to "FileMaker and external server accounts"?
If so, what operating system is your server running? Was external authentication originally working on your FM 11 server? We have been having a problem with FMS 10 which is manifested by several problems: Scheduled backup scripts on the server would start running but never complete (the script just says running), the database server component can't be stopped, users can't be disconnected, external server accounts wouldn't work... those are just the things we've noticed. The only thing that ever solves it is just stopping the FileMaker Service (we're running Windows Server 2003), and restarting the computer. This is a horrible way to restart FMS, but it is the only one that has ever worked. The fix works for some inconsistent period of time before it starts happening again.
Despite all the posts I've seen (and made), I haven't seen a solution to this. I'm not sure it's been resolved in FMS11, but your post makes me wonder.