With some cheap soldering guns often although the quoted wattage is plenty sufficient they are utterly useless at transmitting the heat (I had one that melted its own element housing for instance).

Perhaps the gun isnt up to scratch or perhaps you are not heating the piece before applying solder as Simon suggested?