Set the display order for the node at a number that falls between the display or the nodes you wish this category to fall in between.
For example , if you numbered all you node ids sequentially with no gaps (1,2,3,4,5,etc) the easiest way would be to first add a 0 to each of them (10,20,30,40,50,etc) so that if you want the new category to be the third node listed you could give it a display order number like 25 which will insert it there without messing with any of the other order (10,20,25,30,40,50,etc) .