Here's another tip: This is the the thought process I use for about half my levels, and probably the thought process that you would probably use quite well when you refine it.
1) Start by looking through levels in the original game, in other packs, etc. Find a level with a trick that you like. Maybe two tricks later, but for now, I'll start with one trick.
For this example, I am going to use the "climb-bomb" trick [used in Mayhem 19, among other levels] where you bomb a lemming as it climbs the wall, and makes an indent in the wall. I am also going to show you a Cheapo version of the level I am describing. Now, this level is a very simplified version of what I'm describing; the trick isn't that hard to find, and the level isn't that difficult.
2) In your mind, or on paper, imagine a terrain structure that implements your trick. Figure out a way to make your trick the only way to pass a level. For example, a climb bomb level requires a somewhat large wall in order to work. I also requires, perhaps, a way to use a builder ramp from the bomb hole to perhaps catch a few lemmings that would splat otherwise? Draw a picture of what you want.
3) Place the terrain pieces to design your level. Make it at close to your drawing as you can, but if something wrong, fix it. Plan your tasks, but also add a couple tasks that aren't really needed to beat the level.
4) Play-test the level. Done.
I'll have the two pictures up rather soon.