Here is my list of the top reasons soldering doesn't work well (looking forward to your opinions on this):
1. Soldering tip has oxidized (turned black) and solder won't stick to it. This happens when the tip is left bare while on--a naked tip will quickly oxidize at hot temperatures. The best advice for preventing this is to glob solder on the tip every time you set the iron down. Weller (high-end iron manufacturer) actually recommends holding solder against a new tip the first time you turn it on so that the solder will melt and cover the tip the very instant the it gets hot enough. One of the best guides out there that emphasizes tip care: Weller's HowTo
2. Bad technique: applying solder to the iron, letting it sit there for a while, and then trying to carry it over to the joint. If you let the solder sit on the iron, the flux quickly boils off (the fumes are from flux, not the lead). And without flux, soldering becomes almost impossible. Flux removes oxidation from metals, and it's crucial because solder won't stick to oxidized metals, and metals oxidize very quickly at soldering temperatures.
3. Not enough heat: A 15 Watt iron is fine for small chips, but any larger connectors or wire bigger than 16 gauge will cause problems. 25W-30W is probably fine for most hobby applications. Is there any risk to getting a 100W iron? Wattage is separate from temperature, right? ... depends on the iron. Watch the video on the next page.
4. Dirty or oxidized parts: Bare copper oxidizes relatively quickly (this is why most components are tin / lead coated), so older parts or bare copper that has been exposed for only a week or two can require a light sanding (pink erasers are great) or stronger flux.
Shameless plug: This instructable is an except from a larger guide with many more pictures found here: www.CuriousInventor.com/HowToSolder. There is also a desoldering guide, a review of the cold heat iron, and advice for choosing solder / flux types. And, of course, a store to buy stuff :)
Thanks for any corrections / feedback.