How to update a switch loop to a 3 way switch
This is the proper way to wire the three-way circuit with the switches and lights in the positions you describe. The conventions and wire colors are for the U.S.A. 



Note the black tape (or paint) on the white wires that are used as switched hot instead of neutral. 

The orange lines represent fault grounding wires. These are usually omitted from an instructional wiring diagram, but your 12/3 was wired strangely so I want to show proper grounding. 

A 12/2 cable actually has three conductors in it, two with their own insulation (in different colors), and one bare wire that is only insulated from the world by the cable sheath. Similarly a 12/3 cable has four conductors, three with color-coded insulation and one bare. The bare wires are to be used as fault ground and only as fault ground. Never allow them to carry current during normal operation. 

If your cables have these bare wires, connect them all together and also connect them to everything that looks like it can conduct electricity. If the junction boxes are metal, connect them. If the lamps have grounding screws, connect them. Just ground everything you can. 

You can make an exception for any box that holds a switch; since the frame of the switch is metal and is screwed to the box, the grounding screw on the switch will suffice. Also, in some jurisdictions, ceiling lights do not need to be grounded. 

Note -- the advice in this answer is from a stranger on the internet who is not a licensed electrician and who has not read the applicable ordinances for your location.