I am also having problems with Lion 10.7.4 connecting to a Windows 2003 Server using AFP. Like other people have said, SMB works fine, but we do not like SMB. We want AFP back. All our pre-Lion machines connect to the Windows Server just fine.
I did call Apple and talked to Enterprise Support and absolutely got no where. The guy I talked to (PJ) suggested I update the Windows 2003 server after I told him the famous message everyone has been getting (that the server is not supported by Lion). Well, in my situation, I do not have access to the Windows Server, and now I have Lion machines that are useless. If Apple is going to make a dramatic move like this, shouldn't there be a preference setting in case the user wanted to enable the UAM's to get the AFP server connection back. Disabled UAM's are discussed in a kb Apple support article HT4700 (http://support.apple.com/kb/HT4700).
The steps in the article do not work in Lion 10.7.4, and I tried them over and over with no success. The main point of the article is to enable the UAM's (that Lion disabled), so client-server connections once again will work when connecting to Windows 2003 servers.
I there is no solution, that's fine, but it would be nice to know if there is because I hate using the SMB protocol.