Try this. For NX6 (and 5??) the seed parts are accessed in a different way, through templates. So when the user hits File > New Part, the Templates menu is displayed and the user picks from the list. It will be noted that you are conveniently placed in to Modelling for models, Drafting for drawings etc. This is a setting in the Template file. One of the optional settings is to say that the part will be an assembly, and if this is picked, the Add Component menu is automatically displayed. However, it is possible (and we have chosen this) to not have this available as an option. When the template file is set this way, when a user selects New Parent, you get exactly this error message. So I would look at your Template menu, and if there is not the option for a new part of Type Assemblies, that is your problem.
The file is stored in wherever UGII_TEMPLATE_DIR is pointing, and will have a .pax extension. If you are working under Teamcenter, the file name will start with nxdm_ something.Hope this helps, it's a bit arcane, I know.