For those who need it, from those who give it, is a grid maker plug-in, allowing you to choose the size of the grid, and the ability to preserve the background of your selection.
Updated for Paint.NET 4.0
Download DLL here:
GridCheckerboard.zip
Install the normal way. If that doesn't work, post your troubles here.
For those that are curious, here is the CodeLab source for the effect:
// Title: BoltBait's Grid Maker v3.0
// Author: BoltBait
// Submenu: Render
// Name: Grid / Checkerboar