Tridion Copy / Paste On the same org element raises error TCM54

We are experiencing a strange issue after upgrading from Tridion 2011 GA to 2011 SP1 HR1. When copying components to the same folder, we usually get a popup asking if we want to paste a different name, however in our case we see an error message like this:

/WebUI/Models/TCM54/Services/General.svc/CopyPasteItem failed to execute. STATUS (500): Internal Server Error The page cannot be displayed because an internal server error has occurred.

      

        
        
        
      

    

The only thing visible in the Event Viewer logs are the warnings that are expected (because my test VM gets them too). In fact, we don't see any errors other than the one in the GUI.

When copying / pasting components to a folder:

Unable to paste the item into this Folder. 
Name must be unique for items of type: Component within this Folder and its BluePrint context. Source or sources  of conflict: tcm:4-81455. 

Error Code: 
0x80040329 (-2147220695) 

Call stack: 
UtilitiesBL.AssertUniqueTitle 
UtilitiesBL.CloneItem 
ComponentBL.Clone 
Tridion.ContentManager.ContentManagement.RepositoryLocalObject.Copy(OrganizationalItem,Boolean) 
Tridion.ContentManager.BLFacade.ContentManagement.RepositoryLocalObjectFacade.Clone(UserContext,String,String,Boolean) 
Folder.PasteItem 

      

        
        
        
      

    

When copying / pasting pages into Structural Groups:

It is not possible to paste this item into a Structure Group.
Name and File name both must be unique for items of type: Page within this Structure Group and its BluePrint context. Source or sources of conflict: tcm:5-82986-64.

Error Code:
0x80040329 (-2147220695)

Call stack:
UtilitiesBL.AssertUniqueTitleAndFileName
UtilitiesBL.AssertUniqueTitleAndFilename
UtilitiesBL.CloneItem
PageBL.Clone
Tridion.ContentManager.ContentManagement.RepositoryLocalObject.Copy(OrganizationalItem,Boolean)
Tridion.ContentManager.BLFacade.ContentManagement.RepositoryLocalObjectFacade.Clone(UserContext,String,String,Boolean)
StructureGroup.PasteItem

      

        
        
        
      

    

As mentioned above, these are the usual warnings generated in the event log, but we should be getting a popup, not an error.

We tried restarting the server thinking it was a one-off type of quirk, but that didn't help. I understand that "TCM54", as stated in the error message, refers to code that was run through COM +. Can anyone suggest some tips?