The reason for this is that CO2, like everything else (except water and bismuth), expands when it warms and contracts when it cools. This is the same reason a canister of CO2 will show that it is less full when cold. Even though there is technically the same amount of CO2 in a warm beer as there is in a cold beer (given it is in a sealed container), the effective volume of the CO2 in the cold bottle is lower, as is the pressure of CO2 in the bottle. When the pressure drops, CO2 that is absorbed in the beer (carbonation) evaporates into the empty space in the bottle until the pressure in the empty space = the effective pressure of the CO2 absorbed in the beer.
Basically, you just need to give your beer more time to carbonate. Don't try to carbonate it cold, it is just going to make it take longer. Judge the level of carbonation by the chilled beer, that is how you are going to drink it after all.