That's actually what i originally wanted to do, but i couldn't figure out a good way to implement erasing just part of a square. I may end up going back to it later.

I'm thinking you might have to achieve certain goals before passing a level (things like painting large murals, collecting certain items, etc.) or maybe adding in a points system based on the number of "colors", size, etc. Perhaps also the longer you stay in one area painting the more likely someone is to call the cops, and if you leave an area too long what you've started to paint will get cleaned up or you'll lose reputation points for leaving too many tags half-done. I'd also like to add in some action such as fights, chases, etc.

It's not all very clear yet, but i'll be trying to figure it out as a go along.