Something has to be different than what you say for this scenario to occur in a house that's wired in a manner even approaching code compliance.
The voltage drop on the outlet while the fan is on is normal. The fan is simply using some of the power of the circuit, decreasing the remaining potential elsewhere in the circuit.
You say that the voltage changes at the outlet when the fan is on, but the outlet does not work. This means you are getting voltage at the outlet even when the fan is on. Are you reading anything close to 120V? (anything between 110 and 125v is "normal" household voltage in the U.S.). Do you get significantly more voltage when the fan is switched off? If this is true, my hunch is that the branched connection at the J-box served by the panel is not as continuous as it should be.
With the circuit deactivated at the panel, take apart that junction (hot and neutral), make sure the wires all have about 3/4" of insulation stripped, the wires are all twisted together (you can't rely on the wire nut to secure an extra wire to an existing twisted wire junction), and the wire nut is securely screwed on to the twisted bundle. Tape around the entry to the wire nut for both the hot (black) and neutral (white) wires, then before you put everything back, turn the circuit on and try your multimeter again with the fan off and on.
If it's still cutting out, make sure all the connections in the switch and in the ceiling are kosher in much the same way.
Just a shot in the dark; are you sure the switch isn't a three-way? If it is, then the two terminals at the bottom of the switch are not continuous; you can't hook on to either of them with your new hot wire or with the wire from the panel to the J-box you're hooking into. You should instead hook into the top (Common) terminal (it will be the only one on that end of the switch body), which should be fed from the panel and will thus take the switch out of the circuit path to your outlet. If making that change means that something else is now always on, then you need to find or make a different branch of the circuit for your outlet that is fed directly from the panel.