Trouble connecting to Lion server AFP shares after changing server's hostname

Hello everyone,

I recently changed hostname of my Lion server box (via Server application) and now my clients are having a problem when trying to connect to its AFP shares via aliases. It takes 160 seconds of "resolving alias to <sharename>" before it finally works. Aliases were created by navigating to the server, connecting with "Connect As", providing valid credentials, then navigating one level up and dragging the share icon (blue disk with three white people outlines) to the Desktop with Option-Command.

What is interesting, if I create a new account on a client machine, create an alias, and click on it - it works without any delay, as it was for the clients that are having problems now; so I'm assuming some details about the previous server name got cached somewhere.

The clients with long delay problems can access the shares quickly if they click on the server in the Finder window drawer, then "Connect As" and provide their login credentials - it works instantly then.

I've been digging around quite a bit (deleting Keychain saved Network passwords for any and all references to the server I could find), and also by looking at kerberos logs on the server. What is interesting, the newly created clients I mention above who don't have delay with connecting, don't leave any records in the kerberos log file; but the ones that have 160 second delay do - there's nothing for 160 seconds, and then there is a flurry of activity, as the connection is finally established.

When a client who has trouble connecting uses the "Connect As" method described above, entries in the Kerberos log are created instantly when client clicks connect.

Probably also worth noting that renaming of the server was related to me setting up Open Directory on it.

Any pointers would be greatly apprecited.