Of course the paths wern't correct! Stupid me!
Changing the paths to this solved the problem:
session.move(movedNode.getPath(), destinationNode.getPath()+"/"+movedNode.getName());
I need to read the documentation more carefully:
The destAbsPath provided must not have an index on its final element. If it does then a RepositoryException is thrown immediately. Strictly speaking, the destAbsPath parameter is actually an absolute path to the parent node of the new location, appended with the new name desired for the moved node.
Source: http://www.day.com/specs/jcr/1.0/7.1.7_Moving_and_Copying.html