Rubik's Magic
And I found another thing from my past which has kept me busy thinking about what's its name and where to start looking for it in the first place.
And now with the help of Rubiks.com I've found the Rubik's Magic Puzzle which was another ghost of my mind for quite a long time.
Many hints and descriptions of this 'magic' can be found here. Around 1997 the creators of the puzzle seem to have changed the colors of it. I like the old black and rainbow colors better. Perhaps I'll purchase one but I'd like to still look around a bit, perhaps I can get my hands on the old edition somewhere or can save shipping costs when I order it from a nearer geographic location.