That menu should appear almost instantaneously.

I've had this problem for a long time, even with the previous
installtion of Windows 98. Apparently, the speed of the "New" menu
depends on the number of registered file extensions under
HKEY_CLASSES_ROOT. More registered extensions means slower "New" menu.

This is further explained in the following thread:

Slow 'new' option in Context Menu
http://groups.google.com/groups?hl=e...l enet-ops.be

Perhaps you have a different issue that needs addressing.
Any other menus slow or any problems
navigating through different windows, folders, and so on?
Nothing I can recall at the moment.

Thanks for your reply.