The best bet is to....
Make sure you are using proper LocalTalk cabling to the AsanteTalk box, not just a serial/printer cable.
Switch off the AsanteTalk box.
Start the linux box with netatalk.
Start the mac with LocalTalk/AppleTalk enabled on the printerport
Then once the machine has started up, powerup the AsanteTalk box.
Try nbplkup from the linux box.
Go the the control panel and select AppleTalk or Network depending on if you are OpenTransport or classic and see if that says anything different.
I've had varying success with the AsanteTalk box, it seems to work best when there is an appletalk router already on the network.
If you already have a Mac with ethernet, the control panel "LocalTalk Bridge" seems to work better than the AsanteTalk box.