Figured it out.
The error message is the one from the .webpart file:
<?xml version="1.0" encoding="utf-8"?>
<webParts>
<webPart xmlns="http://schemas.microsoft.com/WebPart/v3">
<metaData>
<!--
The following Guid is used as a reference to the web part class,
and it will be automatically replaced with actual type name at deployment time.
-->
<type name="7F8C4D34-6311-4f22-87B4-A221FA8735BA" />
<importErrorMessage>Cannot import Project Filter.</importErrorMessage>
</metaData>
<data>
<properties>
<property name="Title" type="string">Project Filter</property>
<property name="Description" type="string">Provides a list of Projects that can be used to Filter other Web Parts.</property>
</properties>
</data>
</webPart>
</webParts>
The problem is that the original .webpart file was created on a 32-bit system with Visual Studio Extensions for WSS installed.
However as I'm now on a 64-bit machine VSEWSS is unavailable, and I believe that results in the above GUID not being substituted as I am not using those deployment tools.
Replacing the GUID with the full type name works.
So if you encounter the error message from your importErrorMessage node, then check that your type node in the .webpart file looks more like this (unrelated example):
<type name="TitleWP.TitleWP, TitleWP, Version=1.0.0.0, Culture=neutral, PublicKeyToken=9f4da00116c38ec5" />
This is in the format:
Class, Namespace, Version, Culture, PublicKey
You can grab that easily from the web.config file associated with your SharePoint instance, as it will be in the safe controls list.
Best Answer
Well, it looks like your webpart definition file si somehow broken. The wey i do it is to put webpart into page and then export it. You can do this just by opening webpart galery, which can be located in site settings of root site collection and add your webpart there.
After that just place webpart to any page and use export button in webpart settings. This will produce .webpart or .dwp file depending on your webpart (.webpart is 'new' definition which is used by webparts native to MOSS 2007 and .dwp is for older webparts, but it depends how you have written your webpart)
Then just take exported file and include it into your project. This approach works for me at least.