ok guys i've found smthing that did it for me and since i'm running under 98se also, it could work for you.
The cause of that was the uninstall/reinsall of an nvidia driver. Nvidia create a registry key next to the "New" line registry key and i dunno how it seems to delete that key for new line.
So here 's the solution i found:
Enter windows registry (make a save before if u want but anyway windows save registry at each reboot): start/execute : type "regedit"
In the registry go to :
HKEY_CLASSES_ROOT\Directory\Background\shellex\ContextMenuHandlers
right-click on the directory ContextMenuHandlers and choose new and key
Name the new key as you want, the default name "new key" should be ok
Then click on that new "new key dir"
In the right hand panel, there should be " default" and "no value set"
double click on default and enter the following CLSID key: cut and paste it , with the brackets:
{D969A300-E7FF-11d0-A93B-00A0C90F2719}
then click ok and exit and right click on your desktop: your good old new line has returned

, there's not even need of a reboot for the change to take effect.
I found that somewhere on aforum, icouldn't figure it out myself, hope this will help you!
Peace!