TomZ, thanks for suggesting Der verrückte Laden, I will make sure to check it out!
Unfortunately I know if no great puzzle store in my great town, but here is where some new puzzles can be found from time to time:http://www.werken-spielen-schenken.de/wssimpressum.html
This is a wonderful toy store also for model builders and scrapbookers. Lately I have seen there puzzles such as (I don't remember exactly): Rubik's 3x3 and 4x4, Rubik's 360, Rubik's Code (havn't seen that one anywhere else), Think Fun 36 Cube, many Smart Games as well as Philos tanglement and take-apart/put-together puzzles. Spieleland
in the Schönhauser Allee Arcaden
(S and U station Schönhauser Allee) has a small puzzle section (look for the large Rubik's Cube replica hanging from the ceiling) where I have seen Rubik's 3x3 and 4x4, Rubik's tower, Rubik's 360, Rubik's Magic, Rubik's Race (though not when I was there today), some Smart Games (including IQ Puzzler and Smart Phone) and Think Fun Games, some Philos Puzzles.
There's no need to check out Toys'r'Us, but I have bought some of my Puzzles (Think Fun 36 Cube, Rubik's Delta Ball) at Spiele Max
(toy store chain).
I hope you have a great time here, puzzles or no.