I suspect a bug, I got the one from skull-guys hole and did the puzzle, used the item on it, got the bonus.

Then later I noticed it had un-puzzled itself again.

Am I doing something wrong or does it just randomly reset? It did it again later, and I'm running out of items to do the puzzles.

I haven't tried it (still downloading) but from what I've read elsewhere there's a bug where puzzle weapons reset to unsolved if you solve the puzzle while the weapon is equipped. The official workaround while waiting for a fix is to put the weapon in your inventory and solve the puzzle from there, then re-equip the weapon.

Hope this helps.