Decided to go the cliched route of power-ups and added a few abilities in that Spud can collect to aid him on his travels. At the moment they're in the form of scrolls. Here's what I've added in so far (the names aren't final):
Increases movement speed when you hold down a key. Helps offset the huge amount of backtracking.
Breathing underwater / Gills:
Self explanatory. Replaces the snorkel.
Truth / Perception:
Allows Spud to see things hidden to the naked eye. This replaces the magic lens.
Makes Spud able to push and drag blocks. Probably will have other uses.
Enables Spud to warp to any save crystal that he's uncovered on the map screen. Again, helps with backtracking.
I've got a list of others that may or may not be included like swim (free movement in water), glide (slows falling), high-jump, climb (doubt I'll add this, wall-jump serves a similar function). I'm also thinking about an ability that would be similar to the morph ball out of Metroid and could get Spud through small gaps.
Post your opinions/idea's.