Hi Wasp - this area is fine for any 2D questions or discussions, no need to move anything.
I think your on the right track with the graphics, thinking about Braid and the style in that, and it works really well.
For art packages, well I think there's 2 good options...
1) Paint Shop Pro 9. I got it for free from a website (legally), but I can never find it again. Anyway, it's like Photoshop before Photoshop got all bloated, like Photoshop 4 maybe. I like the way it works, it always feels more accurate to me, especially with pixel art. It's straightforward and should do anything you need.
2) ArtRage. This is a bit more organic and artistic - it's more like a painting simulator than and art package. When I got it, I got it for free with a Wacum Bamboo tablet, it's it's simply awesome with that, has a really good feel to it. Perhaps it would be a plan to look for the same thing - so you'd take your Mario tiles, and use them as guides in ArtRage, then you'd have this neat oil painted look to everything. I think it was only about £40 for the tablet and ArtRage, but if I was doing a project like yours that's the first thing I'd do - it's the best way to achieve the look you want, and isn't a huge investment. ArtRage isn't nearly as good with a mouse, you need to pressure sensitive pen to do it right. The thing I like about ArtRage the most, is that freely rotating canvas! - it's like being able to draw at the best possible angle all the time. Wacum tablets can be fiddly when you have to draw a line at a specific and weird angle - ArtRage lets you drag the canvas around and rotate it to mimic this and it makes a huge difference.
I am the one who knocks...
