Never willing to call a bug a bug, Microsoft support was able to confirm to me that “by design” the importing of the Connections entity in CRM 2011 does not function in a worthwhile manner (as of Feb 2013).
The issue stems from being unable to tell CRM to which entity type you are connecting. For example, suppose you have a Lead record named “Mark Rockwell," and you have a Campaign named “May Promotion." If you use the template available for import for Connections, the only data you can specify in the import is the name of each record, but not the entity itself. So the import file contains “Mark Rockwell” and “May Promotion” as items to connect. In many cases, the file will import fine.
However, suppose in this above example that for whatever reason (and there are many realistic and viable ones) that you happen to also have in your system a Contact with the name “Mark Rockwell.” If so, the Connections import will fail, due to a duplication error. That is, because “Mark Rockwell” is all you can specify in the import, CRM searches the entire system (every entity – how inefficient is that!?!) looking for anything named “Mark Rockwell.” Because it finds both a Contact and a Lead, that import record will fail because CRM’s import utility can’t find what record you really want to connect to. Unfortunately, the import doesn’t allow you to specify the entity (Lead or Contact) either.
Some workarounds are to manually create these Connections, look for duplicates and change names or de-duplicate, or to use specific GUIDs for records in the import file (which is a painful process in most cases). I have found success claims from 3rd-party import tools as well, and of course, creating Connections with plugins via code works fine as well.