What kind of soldering iron do you have?
The good tips don't need any special attention when you first receive them as they have a coating on them that will readily accept solder on the entire working area. High end Weller and Metcal tips should both be like this. They need replaced when that plating cracks. You can usually see the crack on close inspection. Frequent use of solder wick can cause this. The use of abrasive tip cleaners (those metal shaving stuff) will also wear it down quickly. I don't recommend those on Weller or Metcal tips. The "tip tinner" that Radio Shack sells can also destroy these specialized coatings, so I don't recommend it either for these tips.
On Radio Shack and other cheap tips, they need replaced when they're noticeably pitted or when all your solder joints get this frosty look you're talking about. What happens is that the tip starts getting eaten away by the solder and flux. This actually happens pretty quickly. Radio Shack irons are really only suitable for very casual use. Unfortunately, the cheapie Weller branded irons are also of this style. If you have a Radio Shack iron and you're getting frosty joints, I'd just go ahead and replace the tip. They're cheap, and it might fix your problem. Also consider upgrading your iron.
If you're interested in a reasonably priced, good soldering system, I recommend the Weller WES51. I use a WESD51, which is just the digital readout/set version of a WES51. This is a temperature controlled system, and the tips have an Iron/Nickel/Chromium plating that readily accepts solder and does not donate contaminates. Replacement tips (PES51 compatible) are pretty readily available. I usually keep an ETP, ETO, and ETS tip around in addition to the stock/included ETA. The ETA tip is a great general purpose tip, but it's a bit big for 0603 and 0402 passives.
As for RoHS vs. non-RoHS, the non-RoHS stuff is generally considered superior from everything except a pollution POV. Standard non-RoHS PCB finish is leaded hot-air leveled solder (HAL or HASL). This is a very good finish and is compatible with both leaded and lead-free solders. Common RoHS compliant finishes are Nickel/Immersion Gold (ENIG) or Immersion Silver. Some facilities can offer lead-free HASL, which is probably the best option for hobbyist use, but it's not commonly available. If you have to go RoHS, pay for the gold finish: it'll keep forever on the shelf (the silver finish tarnishes), and standard leaded/lead-free solders seem to have less of a problem soldering to it than immersion silver. Just keep the heat on the joint for as little time as possible. Almost all components you'll buy outside China (and even in, nowadays) are RoHS compliant. This usually means a matte tin finish, but sometimes a tin/silver finish. If there's any silver anywhere in the system, it's a good idea to use silver bearing solder.