Nodeblock checkbox not appearing in node submission form

Any of you Drupal Ninjas and Demi Gods encountered this issue before?

I'm building a site based on the Zen Starter theme in Drupal 6.

Successfully managed to get one node to display in a block using the normal Node Blocks process.
However I can no longer see the Node Blocks checkbox when trying to edit content or create new content.

I've tried uninstalling the module, deleting the folder, refreshing it, re-installing it, flushing caches - you name it... but that little sucker of a checkbox still won't display.

The block I originally created is still there and still works. But when I open up the content to edit it - the Node Blocks checkbox isn't there either.