I'm not sure if this is at all the cause of your issues, but I have had trouble with this when either the file being replaced or the file that is replacing it is opened as read only. We use pdmworks workgroup, which causes file to be read only if ownership is not taken. Whatever the cause of the readonly state, though, it seems SW doesn't like to replace references to or from them.
I have the exact same problem with changing drawing model references. After reading Dale Slotman's comments about "read-only" status, I found that if I have write access to both the old and the new model, it will work. I had both models open also but I'm not sure if that's necessary.
Give it a try and good luck!
Dale Stoleman's advice worked for me to. I just needed to 'check out' the part whose reference I was trying to replace so that I had read access and it worked.
the error message could definitely be a lot more descriptive, its more than a little misleading.