Recently many users have been getting failed login when accessing the samba shares. I then looked at wbinfo and it is not returning the full list of users only half of them.

What could cause this?

Can somebody please help with this as it is an intermittent problem that could loose important data.

There could be two reasons:
1. Your winbind cache could be containing corrupt data. You can find this in /var/lib/samba.
a.) stop samba and winbind
b.) Make a backup copy of /var/lib/samba
c.) Delete contents of /var/lib/samba
d.) Rejoin your server to your domain: net rpc join -S <netbios name of domain server> -U [root%<*samba* root password> | <domain admin>%<domain admin password> ]
e.) restart samba and winbind
f.) Time sync is crucial. Always have an ntp client in your member server synching with the time in your domain controller.

or....

2. Your pdc could be running heavy. Check youe domain controller's systems load. A heavily loaded PDC can not respond to your member server's query resulting in having not all the users authenticated. If I am not mistaken, time-out period is 10 seconds.

TIP: Increase the winbind cache time. This way winbind will not query authentication to your pdc often. If your don't add/delete users/groups often try changing it to the equivalent of 1 - 2 days (in seconds of course)

Interflex, did this work?

This worked for me! Thank you very much!

This worked for me after the third try, too. It's crucial to do it in EXACTLY this order! Stop daemons, delete files, add to domain, start daemons. Thanks mar10

ran the following:

sudo pico /etc/samba/smb.conf
then add "winbind cache time = 40" (or at least something greater than 10)
and of course Ctrl "x", "y", and Enter to get out of pico
sudo mv winbindd_idmap.tdb winbindd_idmap.tdb.old
sudo /etc/init.d/winbind stop
sudo /etc/init.d/samba restart
sudo /etc/init.d/winbind start
wbinfo -g
wbinfo -u

which worked, at least for me, using Debian Lenny (but now I'm onto another problem of getting "getent group" and "getent passwd" to list the same results as the wbinfo commands (but with SID and GID I can use to lock down some folders)...

In my case, the tdb files were cached in /var/cache/samba