Samba Winbind User Resolution

Now resolved, this worked for me:

Cleared all Winbind caches and flushed net cache.

Remember to take a backup before deleting anything!

Stop the Winbind and Samba services:

service winbind stop
service smb stop

Clear the Samba Net cache:

net cache flush

Delete the Winbind caches:

rm -f /var/lib/samba/*.tdb
rm -f /var/lib/samba/group_mapping.ldb

Start the Samba and then Winbind services - Note: The order is important

service smb start
service winbind start

Test it by trying to resolve a user.

May be net cache flush will do.

I had to delete /var/cache/samba as well, in addition to malco's answer (on Debian and Ubuntu)