I've experienced this myself on some set command based switches. On IOS based switches, I've not had this problem.
What I found out was happening was that even though I cleared port security, the mac address was still being kept. The switch still saw it on the old port. I had to specify the mac address when disabling port security. Only then did it clear properly. The problem was intermittent. I've recently updated the OS, and haven't checked since then. Perhaps the update has fixed it. I'll check it out.
Try this.
"show cam static"
See if the mac addresses appear in their old port positions. If the do, then try...
"set port security <mod/port> <mac address> disable" on the old port.
Then, re-enable port security on that port.
Hopefully, the syntax is correct. I'm not at work right now.
By specifying the mac address on my ports during the disable, I was able to finally clear it from that port.