Too bad you didn't start this in June 2010 which is when I apparently last played the game. Anyway, I had to fire up the game again, some of the screenshots in TLE didn't quite do the level justice (eg. it didn't clearly show that Classic 2 starts with 2 "trapped" lemmings).
Here're my idea(s) on Classic 1-5, plus 6 so we move forward:
Classic 1: Just jump!
Step up to a better place
Classic 2: Don't forget us!
Prison Break
Classic 3: Security Bypass
Prison Break Part 2 [kinda make sense in conjunction with previous level, as if you've break out of the jail cell and now need to get past the security lasers]
Classic 4: [can't think of anything, let's stick with Clam's]
Classic 5: Don't lose your focus!
Black Widow
Something's getting harder (okay that's really bad......)
The Long Way Home
Classic 6: Downtown [not feeling this one either]
And here's to kicking off the other tribes:
Egypt 1: Just dig!
One floor down
Shadow 1: Mine entrance [this is considering Shadow 2 looks like it's inside a mine]
=======
It's kinda fun, but maybe this is also trying too hard. The random title approach may work better for most of the levels, just like it was done for some of the Lemmings 1/ONML/Lemmings 2 levels.