That would be Stone Age.

___
And since I know that it is, here you go:

[HINT: This is Game Boy!]

Let me just confirm that you were right ;)

i believe you are looking for the name 'Castelian' rather than 'Nebulus' or 'Tower Toppler' ya sneaky git! (But not sneaky enough for ME!)

*edit* apparently it was also "Kyorochan Land" on the Famicom - how many names does this game have?

Apparently many. And apparently not nearly sneaky enough indeed. You are of course correct!

What I had I mind was Castelian (that DOES sound much better than Tower Toppler, doesn't it?).

Castelian is the correct name for the GameBoy version, Nebulus is the correct name for the original game, which came out first on Amiga in 1987.

And may I add the quasi-3D had turned out rather well in this game.

Whoops, sorry, forgot I guess right before I left work!
Here's my attempt at being a bit sneaky

life force

Nope, here's a hint - NOT an officially licensed arcade conversion (OMG how long has it been since I said 'Arcade Conversion' I'll be saying 'Friend of the Genre' next or 'Multi-loader')

R-type?

er...nope

Katakis (if I remember the spelling correctly)

Proof.

Will probably be easy...

Yeah, well done, I would have also accepted 'Denaris' which was the re-release name after they got into 'Great Giana Sisters' levels of trouble by directly ripping r-type off - it was a big story back in 1988 in the C64 / Amiga world, honest!