Had the same problem and finally got it working (it's very hard to find...).
My w2k3 server is a domain controller with Active Directory...
Open the AD Console...right-click domain blabla policies in the left pane, click properties.
In the new window that pops-up you should select the set of policies that your domain is using, choose EDIT.
In the new window that comes up find "windows network". There's something there about "use encryption blabla domain blabla shares", select & disable.
(Forgive the blabla's - I'm not on a server console right now so I can't check the exact names)
You can now use shares the simple way