Here's the test driver and clumsy first stab at a Recognize method.

    class Class1
    {
        const int WIDTH = 8;
        const int HEIGHT = 8;

        [STAThread]
        static void Main(string[] args) 
        { 
            int totalCalls = 0;
            int totalGridsEvaluated = 0;
            int squares = 0;
            int rectangles = 0;

            for (int left = 0; left<WIDTH; ++left) 
                for (int right = 1; right<=WIDTH; ++right) 
                    for (int bottom = 0; bottom<HEIGHT; ++bottom) 
                        for (int top = 1; top<=HEIGHT; ++top) 
                        {
                            Grid grid = new Grid(left, right, bottom, top);
                            
                            Shape shape = Recognize0(grid);
                            //Looked at 4096 grids.
                            //Detected 204 squares.
                            //Detected 1092 rectangles.
                            //Detected 2800 invalid grids.
                            //Called CountBlocksSet 109072 times.
                            //Average calls per grid 26.62890625
                            
                             totalCalls += grid.TotalCalls;
                            ++totalGridsEvaluated;

                            bool gridIsSquare = (right - left == top - bottom);

                            if (shape == Shape.Square) 
                            {
                                squares++;
                                if (!gridIsSquare) 
                                    throw new Exception("Square was incorrectly recognized.");
                            }
                            else if (shape == Shape.Rectangle)
                            {
                                rectangles++;
                                if (gridIsSquare) 
                                    throw new Exception("Rectangle was incorrectly recognized.");
                            }
                            else
                            {
                                // Unknown Shape
                            }
                        }
            Console.WriteLine("Looked at " + totalGridsEvaluated + " grids.");
            Console.WriteLine("Detected " + squares + " squares.");
            Console.WriteLine("Detected " + rectangles + " rectangles.");
            Console.WriteLine("Detected " + (totalGridsEvaluated - squares - rectangles) + " invalid grids.");
            Console.WriteLine("Called CountBlocksSet " + totalCalls + " times.");
            Console.WriteLine("Average calls per grid " + (double)totalCalls / (double)totalGridsEvaluated);
            Console.ReadLine();
        }

        //    static Shape Recognize(IGrid grid)
        //    {
        //        // Implement this.
        //    }
        static Shape Recognize0(IGrid grid) 
        {
            int left = Int32.MaxValue;
            int right = -1;
            int bottom = Int32.MaxValue;
            int top = -1;

            int area = grid.CountBlocksSet(0, WIDTH, 0, HEIGHT);

            if ( area == 0)
                return Shape.Unknown;

            for (int x = 0; x <= WIDTH; ++x)    
            {
                for (int y = 0; y <= HEIGHT; ++y)   
                {
                    if (grid.CountBlocksSet(x, x+1, y, y+1) == 1) 
                    {
                        left = Math.Min(left, x);
                        right = Math.Max(right, x+1);
                        bottom = Math.Min(bottom, y);
                        top = Math.Max(top, y+1);
                    }
                }
            }

            if (right - left == top - bottom) 
            {
                return Shape.Square;
            }

            return Shape.Rectangle;
        }


    }