|When in doubt, add flux? I find most soldering problems are solved with more flux, more solder, or more solder wick.|
Feel free to use a larger iron if you got one; it's a power plug, not a chip. I'm assuming it's not surface mount, so you might be able to cut off the old plug and work on the pins individually, just don't damage the MB.
I joked about adding more solder, but sometimes fresh solder can help remove the old.
Also, make sure the iron's getting hot enough. I don't know how much experience you have with soldering, but leaving the iron touching for 2 minutes probably doesn't do much past the first 30 seconds. I don't have a lot of soldering experience myself, but I tend to work in <10 second increments.
How To Ask Questions The Smart Way