Jim,
From your description it sounds like you have two 110V circuits which share a neutral but have their hot sides on seperate breakers. Am I correct?
This is common. My kitchen outlets are wired this way. Half are on one leg (phase) and half on the other, all sharing a neutral and ground.
In this situation the wire used should be three conductor with ground (14-3WG or 12-3WG). The two hot wires (red and black) should connect to a "ganged" (two-pole, 220V) circuit breaker (15 amp for 14 guage wire). This ensures that the two circuits are not on the same phase. If the two circuits are on the same phase you can have 2X the current in the neutral wire (ie. 30 amps, with two seperate 15 amp breakers on the same phase). Not a good situation.
I would suggest correcting the problem and adding another breaker for your new outlet.
-Jeff