What blender version are you using

This is also occuring with this plugin because the plugin does not place the objects assigned to the group into the scene anywhere (as opposed to append, which does).

http://wiki.blender.org/index.php/Extensions:2.6/Py/Scripts/3D_interaction/CutCopyPaste3D

This is an issue that stems from the fact that it is (presumably) impossible to remove an object from a group causing a recursive usage scenario. It appears to be not possible to remove an object from a group in the UI other than from the Properties panel when said object is selected. However, it's not possible to select a deleted object.

Essentially this appears to be an issue of an object not being removed from a group though it doesn't exist anywhere in the scenes.

To accomplish this orphaned scenario. Append an instance of a group (an empty duplicating a group). This will append the instance and the contents of the group. Delete the instance and the contents with one operation. Normally, this will remove the objects from the Datablocks view of the outliner, because they will not have a user, in this case this recursive orphaning occurs.

This is with 2.74 3-31 release from the main site and has been occuring since atleast 2.65, but presumably during all of Blender's life.

You can append the test duplicating empty from this provider file.

I have a file that has materials caused by workflow as well. I don't quite remember how these materials accumulated these ghost users but I will try to remember.

In addition, this plugin:

http://blenderartists.org/forum/showthread.php?282550-A-new-tree-add-on&p=2878164&viewfull=1#post2878164

May be interacting with the algorithm that culls recursive orphaned objects as relevant to this error.

I think that I can delete it in the following procedures.

This is the result that I deleted from group_paste_error_consumer.blend.

I think this can even be done quicker by selecting ´orphaned data' in the outliner and clicking 'Purge all' (but you need to do that twice)

The addon appends a bunch of materials and particle systems from a bundled library but does not instance any objects in the scene. So all those items are in fact immediately orphaned, unless the user selects one of them to use on a tree object.

Now any objects with zero users are purged on saving the .blend (just like when you click purge all) but this is not done recursively: the object for example are purge but leave their associated meshes with zero user in turn and these are not purged (unless you click Purge all again).

So the bug (if it is a bug, their might be a good reason for this behaviour) is that purge-on-save does not act recursively.

For anyone who has come across this issue in 2018:

In my case, a linked group of a shrub model was preventing the same model from then being appended, and it seemed nearly impossible to delete the offending group. Well, it is not impossible! :-)

In the Outliner, select "Blender File" for type of data to display, and inside "Groups", right-click on the offending group and press Delete. You may need to save, close, and re-open the .blend file. Then you will need to scroll down to the linked data section (identified by a Document Icon with an Arrow), right-click it, and select "Delete". Again, you may need to save, close, and re-open the .blend for the changes to take effect. Now you should be able to append the file as normal. :-)

I thank God for a much simpler solution to this issue. Posted answer on StackExchange here.