Sharepoint - "The type is not registered as safe" when trying to add a web part installed by a WSP

Sounds like you are missing the <SafeControl> element from your package. Normally it is added for you if you create it in VS2010. But if your web part/control is in another assembly you may have to add it manualy

http://msdn.microsoft.com/en-us/library/ms412965.aspx

Something like this should go in your Package.Template.xml file (Solution explorer -> Package -> Open -> Manifest -> Edit Options)

    <Assemblies>
      <Assembly
        DeploymentTarget="GlobalAssemblyCache"
        Location="Text">
        <SafeControls>
           <SafeControl
             Assembly = "Text"
             Namespace = "Text"
             Safe = "TRUE" | "FALSE"
             TypeName = "Text"/>
        </SafeControls>
      </Assembly>
    </Assemblies>

Can you tell us a little about what controls/webparts are in the wsp?

Example default package preview has this:

<Solution xmlns="http://schemas.microsoft.com/sharepoint/" SolutionId="7905031d-87a1-47b3-b631-c93daff7e4c7" SharePointProductVersion="14.0">
  <Assemblies>
    <Assembly Location="SharePointProject1.dll" DeploymentTarget="GlobalAssemblyCache">
      <SafeControls>
        <SafeControl Assembly="$SharePoint.Project.AssemblyFullName$" Namespace="SharePointProject1.WebPart1" TypeName="*" />
      </SafeControls>
    </Assembly>
  </Assemblies>
  <FeatureManifests>
    <FeatureManifest Location="SharePointProject1_Feature1\Feature.xml" />
  </FeatureManifests>
</Solution>

Visual Studio has a bug where changing the namespace of your class does not update the manifest file of the installation package. Then when you install the safe control and execute your webpart, it is missing due to a namespace mismatch.

For example:

<SafeControl Assembly="Sharepoint_Native_Indicators, Version=1.0.0.0,
                       Culture=neutral, PublicKeyToken=cd7250552f7daf2e"
             Namespace="XXXXX.YYYYYY" TypeName="*" />

Dont forget to check the SharePointProjectItem.spdata file too. Most of them miss this. The namespace here may not get updated if you changed it in just the code files.