Chris Thomson's answer makes some very good points about the overall quality, and Leopoldo Salvo's answer points out several hidden issues with the timer(s) and event handling. My comments will be more about alternative approaches to various parts. Not much code, more of a reinterpretation of the stated task.
The first thing I notice is that each update creates an entirely new grid. Even window resizing. It's a simple solution, but a pretty brute-force one.
A simpler solution is to let the browser do a lot of the work:
Make the container absolutely positioned in CSS, and make it fill the window (e.g. give it a 0px offset from all of the four sides).
Then style each cell with float: left, and all you have to worry about is their width and height. They'll automatically flow to fill the container, without you ever having to calculate their position.
And use percentages for the cells' width and height. That way, you never have to worry resizing either. You'll simply have a flat list of DIVs that automagically arrange themselves as a grid and fill the window.
This also makes it much simpler to have just 1 Grid instance that you update, instead of constantly destroying the entire thing, and building a new one. Here's a small example that does all that.
Now, another thing is that the task is unclear: Must the "context menu" be built entirely in JavaScript? The grid obviously must be, but the options aren't dynamic in the same way. I mean, if it's OK to use predefined CSS, and the page isn't supposed to do anything else, I'd absolutely create the options menu in the markup, because it's just easier, cleaner, and much more maintainable than using the DOM. All you'd have to do is hook up some event listeners, and bingo.
Yes, there'll be a lot more coupling between the markup and the javascript, but as mentioned it's already coupled to the CSS anyway, and I the task, as defined, doesn't prohibit it. In terms of simply solving the task, adding the extra coupling just makes things simpler. There are many ways to complicate the task, but there's little reason to do so if it isn't absolutely required.
A completely separate issue is that "context menu" usually means a right-click menu - but building such a thing is pretty involved, and would seem out of scope compared to the other parts of the task.
Some other stuff I happened to notice:
On the timed updates, it'd be better to simply loop though and update the colors of the existing DIVs, instead of removing everything and building a new grid. The number of elements or their positions haven't changed, so it's really only a question of setting the background color.
Speaking of, you're working too hard to get a random color. Here's a nice one-liner you can use instead:
'#' + Math.floor(Math.random()*0xFFFFFF).toString(16);
Make the container absolutely positioned in CSS, and give it a 0px offset from all of the four sides. That'll make it fill the window (in modern browsers). Then style each cell with float: left, and all you have to worry about is their width and height - they'll automatically flow to fill the container.
You're using a form for the "menu", but you're only handling the input when the button is clicked; not when the submit event of the form. The button doesn't submit the form either. As such, the form isn't really necessary - it could be any element. A form is of course semantically correct, but it should be used to your advantage.
The way the form is being built also feels too complicated: Much more can be accomplished in CSS. The input and labels do not need classes, since more generic selectors (e.g. form input[type=text]) will be enough to style the correct elements.
