Well, let's start with the obvious. When entering the username and password, are you entering the info for a user on the machine you are connecting to? For instance, if you're on the G4 and connecting to the iMac, are you entering info for a user on the iMac? It's easy to enter your own info by mistake (I do this from time to time as the Connect to Server dialogue always enters my long name in the username field).
If so, I suggest trying only the long form of the username. For some reason, I've had OS X hiccup on me when trying to connect with the short name of a user. It's probably just my machine though (let's just say I have a date with DiskWarrior before I install Panther).