I think your problem might be that your region limits. When you create your grid, extend the region limits so that you are absolutely sure the whole polygon is within the grid.
Make sure there is only one polygon in the shapefile.
It may be necessary to simplify the verticies of the shapefile. You could use a Simplify and limit the space between vertices to 5 ft 1.2 m or something like that. That will create less verticies to intersect to the grid.