I haven't tried it with TestStand 2012, but with earlier versions, but I think the following would work...
When you distribute your new step types (after setting them up in the Menu Editor) also distribute the TestExec.ini file (from the Cfg link (c:\C:\Documents and Settings\All Users\Application Data\National Instruments\TestStand XXXXXX\Cfg)) Where XXXXXX is your particular version of TestStand. This file holds the type menu order (as well as a load of other TestStand settings.) It might be best to get the customer to send their TestExec.ini file, you update the menus and send it back with your new step types.)
Hope this helps,
Brian