Why isn't solder melting at 370 °C?
Are you sure the tip is actually getting hot? Not just what the stations sensor (which is probably nowhere near the actual tip) says. Try touching it to a small block of wood and see if it smokes/chars.

Does the solder melt if touched only to the iron tip, not to the joint? It sounds really that the tip is not getting hot enough, or, that the tip is too small for the joint being soldered (not enough thermal mass) and so applying it to the cold metals of the joint is robbing it of its heat capacity and cooling it down.

I would also obtain some good quality solder such as Kester or Multicore - the stuff supplied free with the iron (im going to guess its a chinese unit?) is likely rather poor.