Moving one object causes other to move another (already tried unlinking)
I had proportional editing on.

If you ever think your objects are acting as though they were linked and they aren't be sure to check if you haven't by mistake turned on proportional editing. Otherwise you may end up with situation like the one described above.