Flux is important. If you aren't using flux core solder, that could be part of the problem. Flux cleans the surface and it's easier for the solder to stick. (Flux also comes separately and it a wide variety of formulations.)
If flux isn't the issue, then it absolutely is heat. I tried to Google for a picture of the "metal surrounding the CPU", but I couldn't find one. From your description, it sounds like that metal is still sinking too much heat away which also wouldn't allow solder to flow.
Soldering to larger metal pieces is always a challenge. You likely need a lot more heat applied for the shortest time possible. Another option is to heat up the entire board with a hot air gun first, but I suspect that is not an option for you.
Big soldering tips can be used to flow as much heat into the part as fast as possible before the heat gets a chance to spread out.
(A picture of your problem would be a nice-to-have. I am not familiar with your exact components, but I solder things quite a bit.)