ArcGIS ERROR 000824: The tool is not licensed in arcpy

I try to run the Zonal Statistic as a Table through arcpy and it gives me: ERROR 000824: The tool is not licensed.

Here is the doc for the function: http://resources.arcgis.com/en/help/main/10.1/index.html#//009z000000w8000000

I have tried including the line where it checks for my spatial analyst extension:

arcpy.CheckOutExtension("Spatial")

but that just leaves the script running for a long time, way longer than it should (10 minutes+ on a 250Mb raster!)

I was hoping anyone else has a workaround/fix? Thank you for your time!

I have installed 10.1 Service Pack 1. I have checked and enabled all the extensions. Furthermore, I have the advanced ArcInfo version.