So, it seems Apple broke Windows Filesharing / Samba with the 10.4.5 update on Intel-based systems. Windows clients are unable to connect to OS X shares, because the server refuses the password.
There are several threads describing the issue in detail:
http://www.123macmini.com/forums/viewtopic.php?t=4555
http://discussions.apple.com/thread.jspa?threadID=401714&tstart=0

Here is a temporary workaround for the problem:
You’ll have to change the authentification settings on your XP/2k box and here is how to do that:

Start -> Run “secpol.msc”
In the tree open and click Security Settings -> Local Policy -> Security Options
Scroll the left pane down to ‘Network Security: LAN manager authentication level’
Change this to ‘Send NTLMv2 response only’

It works for me. Please let me know, if it works for you too…

Update: Apple has released OS X update 10.4.6 which resolves this problem.