In all my years as an electronics guru I swear (and I'm not kidding I've tried it all) I still like good old fashioned Radio Shack 60/40 thin. I have book and books and catalogues from over a dozen of my favorite suppliers, but when I need solder I run to RS. It's this one BTW and it flows, cools, and shines hella nice
General rule of thumb is the thicker the conductor and the higher the surface area the more heat you will need. For your deans and 13 ga. noodle wire (for example) a minimum of 40 watts is recomended for your iron.
Lightly scuff the flat surface you will solder to (180 grit sand paper is suggested) and place the iron tip on the surface. Try and angle the tip so you get the maximum amount of tip surface area making contact with the flat surface of the deans. For instance if your tip comes to a point on a 45 degree taper, hold the iron 45 degrees against the deans mating surface. Make sure your iron has reached full temp, hold there for about 5-10 seconds, and place the solder against the area WHILE keeping the iron there. DO not place it on the tip itself. The idea is to get the area you are trying to solder to hot enough to melt the solder itself without touching the iron tip. One you have achieved this the solder will wick itself onto the part and leave you with a nice 'tinned' application.
Now tin (flow solder to) the wire itself. Be sure the solder is wicked up into the strands of the wire and not just on the surface. It make take a second or two to do this and the wire will get HOT so it is suggested you hold it with a glove, a vise, pliers, or you can just be like me and grit your manly teeth, bear it, and burn yourself so many times that you barely feel anything on your fingertips anymore (hint: don't be like me) Trim you finished work up to about 1/4" in length.
If you did this right, you will have two thoroughly tinned surfaces to mate. Place the tinned wire against the tinned surface of the deans plug. Place your iron atop the tinned wire. You have a sandwich going here, the deans surface on bottom, the wire in the middle and the iron on top! (kinky!)
Now we wait.. and wait, and wait.. the tip will start to melt the solder that was wicked up into the strands of the wire (don't press too hard here or you will flatten your wire). Once the heat has passed to the other side of the wire it will begin to melt the tinned surface of the deans. The end product will be a perfect flow of solder joining the surfaces. Pull your iron away and give it the time it needs to cool naturally! No blowing on it, or fanning it, etc.
Try and go through the motions a few times prior to actually doing it. Arrange a good and non-burning method to hold things while you solder them.
Look at devices like 'helping hands' that are relatively cheap and can be arranged to hold the wire, the part, or both while your hands are free.
Aside from all that, I think your not properly tining your surfaces first. Follow my tips and you'll be soldering like a pro in no time. Any questions?