Having trouble soldering headphone wires

You should use a wire stripper or a pair of pliers to strip insulation from wire. Small wires can be stripped with your bare hands: just pinch the insulation with a fingernail and yank it off. If you catch it just right, the insulation tears and slides off, but the conductor is left intact.

It sounds like by burning the insulation, you have fouled the metal with the products of combustion of the plastic. This layer will prevent the solder from flowing onto the metal and bonding with it. Even if the plastic was completely vaporized, it's likely that the metal oxidized. Solder does not like oxidized surfaces. To solder, you need clean surfaces free of oxidation or other residue. (Other than soldering flux. Speaking of which, you should have some and use it!)

One of the functions of soldering flux is that, being mildly acidic, when it gets hot, it etches away the thin layer of oxidation from copper. It will probably not eat through the carbonated remains of burnt insulation, however. Still, it is worth a try. If flux doesn't cut through, then just cut a piece off the end of the wire and try again, and this time strip it mechanically rather than, err, pyrognostically. :)

Update: if the wire insulation is just a fine lacquer (similar to what is used on wire used for winding voice coils or transformers), it may be possible to solder with the lacquer in place, with better results than torching the lacquer. Some hobbyists spray lacquer on DIY circuit boards, without covering the solder pads, and solder right through it anyway. It may also be possible to remove the lacquer by using a solvent such as acetone.

Usually what I do is to hold the iron tip with the solder on the tip of the wire for a while, until I see that the solder melts on the wire. That means that the protection layer is gone, and then I put some new solder on.

It takes a few seconds before the coating melts, be careful to have some headroom to avoid melting the rubber coating.

After soldering, remember that you removed the insulating layer, and you have to replace it with heat shrinking pipe or something else.

You don't use flame for reaching bare metal - what covered the metal will burn and combustion products will coat the surface. You have to mechanically clean the surface by using something like a knife or a piece of finest sandpaper.