The error does indeed indicate that authentication is failing.
Firstly, open gitosis.conf on the server and check that you are a member of the group containing gitosis-admin repository. It should show something like.
[gitosis]
[group gitosis-admin]
writable = gitosis-admin
members = user1 user2
The member name must match with a public key in /keydir before access can be made.
Secondly, you do not say how you are connecting from the Windows machines. If you are using Git under Cygwin, make sure you are correctly loading the private key. If you are using MsysGit with Putty, be sure to load the private key before connecting as well.
There is a small gotcha if PuttyGen is used to generate key pairs, and that is the default format is different from OpenSSH which you are probably using. Copy and paste from the top window, or alternatively edit the multiline public key file to read like this.
ssh-rsa AAAABB...KEYBODY...ONLkQ== user1
Lastly, make sure port 22 is open in any firewalls if that is indeed the port you are using.
A more comprehensive description of how to set up a Git server with Gitosis on Windows, can be found at here
I recommend the use of MsysGit from windows, as it gives better integration into the Windows environment. TortoiseGit and GitExtensions both use MsysGit as the backend, and provide nice Gui's and explorer shell extensions. GitExtensions full installer will provide the windows user with everything they need.