One possibility is that the burnt wire might have damaged other wires inside your case - specifically the one to the power button. If you can, try shorting out the jumper on your motherboard that hooks to the power switch with a screwdriver. If it comes on 100% of the time, that's your problem, and you should consider getting a new case.

Also, the new fan might be pulling too much power from the power supply if you have a lot of other devices. Not having enough power can cause motherboards to do funny things.

When it comes to the electricity, people tend to have a wrong approach. Actually the opposit one. (this goes for PSU powe output also) In your case the wire is not a cause but a symptom. It's caused by too much of a electical flow than it can endure or reduced capacity of the flow on behalf of the wire. If the flow is increased than you might have burnt part or shorted circuit (for ex. loose motherboard touching the support panel or s screw stuck between 2 solders). If the wire's capacity is impered (cracked wire) than it needs to be replaced.

You will have to be more specific of what this wire is connected to.
You said it is connected to the front of the casing. Is it a power switch, LED display, LED diode, case fan, beeper, HD, DVD-CD, reset button...?

500 W PSU is more than enough for the new fan. The amount of power generated by the PSU is amount of power that is beeing drawn from it. So, if you have system that needs 100 W of power, your PSU will generate 100 W of power. 500 W is the LIMIT VALUE that can be generated by PSU. (500 W ~ 0.5 Horse power = a lot for the PC)

Tower beeing affected by it's position is suggesting that you have either cracked wire (one that fryed), cracked solder or metal thing loose on the motherboard.

The change of fan can cause your bios alerting you of the fan RPM's. When I built my PC I bought bigger, better and more powerfull colling than included with CPU. I had to change bios settings regarding alert level of CPU fan's RPM's because the new fan works on lesser RPM's (1600) than the original one (2500, I think). I belive that you will have to do thhe same.

I had a computer repair job similar to this the other day.
The computer would work fine and then switch off randomly (may last 2 mins, may last hours) and unable to power back on until it was left alone for a while. When I DID try to power it back on, fans would start however no post beeps or video.

In the end it turned out that it was a bad power supply, which damaged the motherboard and CPU.

The powersupply was failing and was sending spikes of 18volts intermittantly (should only be 12volts) which caused the restarts and failures.

It sounds like this might be the problem and may explain why your wire got burn as it got too much voltage though it.