Chances are the ice is colder than 0ºC. I'm not really sure what the typical operating temperature of a home freezer is, but I would imagine it is something in the -15 to -20º region. The ice cubes should retain that temperature (or close to it) and therefore will not merely be at the freezing point of water.
Also as an aside, it may be a wise idea to crush the ice, sprinkle some salt on it then shove your can of beer into the crushed ice. I really haven't tried that method myself, but I wonder if increasing the surface area of crushed ice would be better.
The surface area of the ice is largely irrelevant, and also the exact reason salty ice water is more effective than just ice water or even just a bunch of ice itself.
Reason being, ice on its own, regardless of how finely chopped up it is (make ice shavings out of the ice, still not as effective), has less surface area in contact with the warmer bottle, and thus less capability for thermal transfer.
With salt added, even just ice added directly to the salt with no water originally (actually, this is ideal), what happens is you get a higher temperature water than the ice itself, but now with greater surface contact.