First -- the original wiring configuration was most likely a 300.3(B)/310.10(H) violation due to the hot and neutral taking different routes in addition to currently violating 404.2(C) due to the old-style switch loop -- what you have currently, though, is also a Code violation, but of section 210.70(A)(2)(c):

(c) Where one or more lighting outlet(s) are installed for interior stairways, there shall be a wall switch at each floor level, and landing level that includes an entryway, to control the lighting outlet(s) where the stairway between floor levels has six risers or more.

Fixing this without re-pulling travelers is possible, though, thanks to a gadget called a relay. You, or your electrician if you feel more comfortable having a pro do this, will need:

• 14/3 NM cable, sufficient to run from the light to the existing upstairs switch
• Wirenuts capable of connecting 14AWG to 18AWG
• A RIBU1C SPDT relay-in-a-box
• A plastic 1/2" conduit locknut.
• Cable clamps as needed
• Short lengths of 14AWG white and black wires to serve as pigtails

1. Turn off power to both circuits -- the downstairs circuit at the main panel, and the upstairs circuit at the subpanel.
2. Open the boxes for the light and both switches.
3. Remove any cable clamps that were holding the 14/2 from the light to the upstairs switch in place.
4. Disconnect the 14/2 from the light and the upstairs switch, as well as the box ground pigtails.
5. Connect the new 14/3 to the old 14/2 so that when you pull the old wire out, you pull the new wire in.
6. Pull the old 14/2 from the light to the upstairs switch out (box fill issues prevent us from leaving it in place).
7. Run the 14/3 from the light to the upstairs switch, and install it in the boxes using the new cable clamps.
8. Connect the 14/3 to the light as follows: red -- open terminal on light, black -- wirenutted to the hot, bare -- connected to the ground bundle.
9. Disconnect the incoming white wire from the light, and connect it to the new white and the white pigtail with a nut. Connect the white pigtail to the light.
10. Knock out one of the 1/2" (small) conduit knockouts in the upstairs switch box.
11. Thread the wires of the RIBU1C through the conduit knockout from the outside, and screw it to the conduit knockout, using a locknut to secure it on the inside. (You will have to remove a bit of drywall to install it -- there is nothing in the NEC that prohibits an arbitrary device from being installed in an inaccessible location.)
12. Remove the switch from the upstairs switch box.
13. Remove the switch from the downstairs switch box and replace it with the switch from the upstairs switch box. Wire the new single pole switch as follows: old traveler 1 -- switch common terminal, old traveler 2 -- switch switched terminal, old hot -- cap off with wire nut.
14. Install the three-way switch from the downstairs switch box into the upstairs switch box, wiring it as follows: common terminal -- black pigtail, traveler terminal 1 -- blue wire from relay, traveler terminal 2 -- orange wire from relay, green ground terminal -- ground bundle (with box ground and ground from 14/3 incoming -- the RIBU1C needs no ground, as it's in a plastic box)
15. Wire old traveler 1 to the black pigtail and the incoming black wire from the 14/3 cable,
16. Finish wiring the relay as follows: black/white wire -- old traveler 2, blue/white wire -- cap off with wire nut, yellow/white wire -- white wire from 14/3 cable, yellow wire -- red wire from 14/3 cable
17. Put the boxes back together.
18. Turn the upstairs circuit back on -- the downstairs circuit has been removed from the picture entirely, so it can be left off.
19. Enjoy your new 3-way switch!

Note that while this setup may not appear to fix the 404.2(C) issue with the current configuration, it falls under 404.2(C)(5) as the neutral is available in the upstairs box:

(C) Switches Controlling Lighting Loads. The grounded circuit conductor for the controlled lighting circuit shall be provided at the location where switches control lighting loads that are supplied by a grounded general-purpose branch circuit for other than the following:

...

(5) Where multiple switch locations control the same lighting load such that the entire floor area of the room or space is visible from the single or combined switch locations

This is a guess!!!

This is only a guess. Further investigation is needed to determine how the circuit is wired, and nothing further should be done until you have a complete understanding of the current wiring.

Based on your description, this is how I think it may be wired.

If this is indeed the case, then changing the wiring as follows, should get things working.

Notice I've swapped the black and white wires at Switch 2. I've also swapped the black and white wires from Cable #3, in the first switch box. Finally, I've marked the white wire from Cable #2 at both ends, to indicate that it is being used as a ungrounded (hot) conductor.

WARNING!!!

This answer is only a GUESS. You'll have to verify this wiring yourself, before making any changes. Trial-and-error wiring is not safe, and should never be done.

If you need further assistance once you have more information, please comment on this answer. I will be happy to help you.