8 years later and this problem still exists with ArcMap 10.5.1!
I have found a 'fix' (actually a work around) that resolves the problem... at least in my case...
I found that if I exported my source layer to a new feature class, added the new feature class to the map, and then used this new feature class as the source layer, the 'Grid Index Features' works fine.
I had a similar problem with the 'Strip Map Index Features' (different error message), and this same work around fixed it for 'Strip Map Index Features' as well as for 'Grid Index Features'.
I haven't done much analysis on why this may be, but my original source layer had a definition query. I have found that some ArcMap tools do not play nicely with layers with a definition query, and some do not play nicely with layers with a join. In such cases, I always export to a new feature class (or in arcpy, use 'FeatureClassToFeatureClass_management() to create a temporary 'in_memory' feature class), and use the new feature class as the tool input. Then delete the new feature class when done.
I hope this helps some other people who are experiencing trouble with this tool.