Very good idea to practice, practice, and practice some more on salvaged boards until you get competent with new tools. You didn't notice the solder had reached the molten state because there's so little of it used to solder components.
The typical lead-free solder has a melting point around 217 degrees C, so you'll have to get the leads and pads up to that temperature before trying to remove the component. The reason why you need a much higher temperature is because you want to get the solder joints to the melting point as fast as possible. If the hot-air gun is set to a much lower temperature, it'll take a longer time to reach the melting point. The longer the time to raise the temperature of the leads/pads will increase the overall temperature of the component, possibly past the point of destruction. So the technique is to heat it up fast, remove the part and hot-air gun, then put the part where it can cool off.
Now, if you're removing a part that's already fried due to some other reason, no worries then. Just don't damage the board by overheating the pads and causing them to lift off. If that happens, your headaches are just beginning on this repair.
There are a couple things that could be happening here 1) that you just haven't got the temps up high enough or 2) you actually are on your way towards board killing.
I'll just touch upon #1 and dig a little deeper into number #2.
Firstly; The temperature at which a component lets go when the solder reflows is to some degree dependant upon the heat flow away from the pads. A component that is thermally isolated will pop off way faster than something that is heat sinked. In general it is better to use higher heat and way shorter times than it is to slowly approach reflow temperature and then start prying away. This is something that is learned by doing and practising.
Secondly: learn about the eutectic point of solder, understand it. In summary an alloy of two materials melts at a lower temperature than each of the consistent parts. There is an ideal mixture ration at which the melting point is a minimum. Solder is such a eutectic mixture.
Here is a diagram lifted from Here
I won't go into too much detail on the diagram, but it is notable that you can get your alloy to melt at significantly lower temperatures and more particular to the case at hand, you can have a liquid/Solid mixture appear if you heat it up to much or hold it at a slightly raised temperature for too long. If you hold the melted alloy at a higher temperature too long it starts to de-alloy. When it de-alloy's the temperature required to remelt and form an eutectic mixture increases.
And this is what typically happens. Frustrated engineer tries to desolder a component. for some reason, (like she forgot to reflow all the pads) and the device stats firmly attached,In fiddling around she holds the melt at slightly too high of a temperature whilst trying to pry the component off the board. Soldering iron bumps the temperature up higher (unknown to the frustrated engineer). She gives up and allows the solder to re-solidify. The cycle repeats with the remelt temperature going higher. The solder starts to look like crap, shiny surface is now textured, but now our engineer is doggedly pursuing full war against the evil chip and doesn't notice the grainy texture. Now, the soldering iron can't get to a high enough temperature to reflow it at all, but the engineer is pouring the heat on. The chip gets scorched, the FR-4 starts to delimitate and there is a smoking crater left. It all sounds dramatic, but it happens too often.
First step: Stop, look at the pads closely and look at the solder. Is it changing appearance? If so, add new clean solder! This new solder will allow the old de-alloyed solder a "seed" with which to regrow into a proper eutectic mixture. Allow it to recool and check to see if you've got good solder joint formation and sheen (but with almost certainly too much solder on the pads - c/w bridges).
If you haven't over heated the chip you now have a chance to reset your reflow attempt and start over.
Other pointers:
The very best way to desolder large and complicated packages whilst saving the board and the chip is to use a bismuth based desoldering alloy. It has a very low melt temperature and is normal solder is very soluble in the melt. This allow you to use a lot lower temperatures and to forma a puddle of solder eating melt on your board. It works wonderfully but is very expensive.
To save the board with large packages, I'll just dremel or snip the leads off of the package and then reflow each pad individually.
To save the board and chip I will, if possible, pry the leads up and by bending the lead up towards the lead frame. It ends up looking ugly. You also have to add solder during this to re-alloy the solder.
Best Answer
You need to get the PCB up to temperature evenly enough that the solder melts all the way around -- if you don't get all the solder melted all at once, then the solid stuff will always hold the chip up and it'll never work.
For a hot-air station, this means either getting a tip that blows hot air evenly over all of the chip, or playing the tip in an oval around the chip, with some extra attention to the board side (because the board will wick away heat).
It can help a lot to take a piece of tin can and bend a 'U' or 'L' shaped piece that surrounds the chip and sort of holds the hot air in the vicinity of the chip.
An alternative with any sort of package that has legs sticking out like that is to clean the PCB off until the pads are just tinned. Then tack the chip down in two corners, and solder it on leg by leg. If it's too fine a pitch to do that, just get everything soldered, even if you get solder bridges -- then go back and clean off the solder bridges with solder wick. The more magnification you can get when you're doing this, the better.