Windows

I assume that you must be using the wizard to add the printer to the notebook. Now can you use the network neighborhood and access the printer? If you do, double click on the printer and you'll get a message "Before use, the printer must be installed, install it now?" and see if you can install that way. Will not resolve the issue, but will get the user up and running while you look elsewhere.

Good luck!

A shot in the dark.
The username is denied access somewhere in the NT security system the resource(s) you are trying to get to. Verify that the user has rights to logon to all the required servers. One thing I have seen is netowrk administrators will deny login access to a server and won't realize what happened because he/she thought they denied local login.

On the server which contains the print queue open User Manager (for Domains). Select 'Policies' from the top menu, then 'User Rights' and verify the user has rights to 'Access this computer from network'. There are other places which would prohibit access to resources such as the print share itself, the drive (if it's NTFS) and the drive share. Denying user access to anything, in my opinion, causes more problems than it's worth so it is my policy not to deny user access to anything. I just give users access to what they need.
Hope this helps.

The Win98 client may be having difficulty downloading the drivers from the NT server. Explicitly share (and give appropriate permissions to) the WINNT\System32\Spool directory (and sub-directories) on the server.

If the problem is long names for shares, why not create a second share for the same printer (I do it all the time), and give it a shorter name for the 98SE laptop? That way you don't have to deal with the machines that are working fine, but have a secondary place for those that require shorter names.

If, per chance, theh printer(s) in question are HP Deskjets, it may be that you need to get the "corporate lan" drivers from HP.com. These printers ship with "home user" drivers intended for use with a single, local LPT port and do not work reliably if you try to share them. Especially, watch out for the 9xx and 7xx series of printers, as these drivers were not all included with Win98 (SE didn't have them either).