You need a lot of ice to fill your esky, and little cubes take a while to add up and melt pretty quickly because of their size. For bigger, better blocks of ice, try using a milk carton instead of an ice cube tray. The Guardian has the details:
Keep drinks cold at a barbecue or party with ice blocks made from empty milk cartons. Rinse them, fill them with water and put them in the freezer. Peel away the container when you're ready to put them in the punch bowl. If you intend to use them as cooler blocks, leave the container in place.
It's worth noting that the material is probably relevant here. Paper milk cartons work well because if the ice expands, they'll just rip.