Only just getting around to responding now, busy evenings.
@Rory: I really like the idea of having the "difficult thing" and then planning around that. I think part of my problem is getting overwhelmed of where to start. Is the exit to close? To far away? Is the level to small? Too large? Are there too many traps? And so on and so on. I like the idea of saying "Ok this level will have lasers that will fire in a certain pattern and you need to jump through them" and then build out from there. Get the core aspect of it working and then add to it. I think that will help a lot.
@DravenX: Seems quite a few of you all start with pen and paper first. I have a pile of printer paper in front of me right now so I'll start sketching and see where it goes!
@kayin: I really like the "try and vary these shapes because that maximizes the effects of spatial memory in the player" note. I think I've found myself constantly battling with this as I tend to pick out boxy repetitive patterns. I'll check out VVVVVV and...wait...you did "I Wanna Be the Guy"?! Nice
! Ha, I was already using your game as reference
Awesome feedback guys, I really appreciate it.