Addictive Puzzle Games that aren't Tetris

[shadobeni]

The only ones I ever put in significant amounts of time into were Dr. Robotnik's Mean Bean Machine and Chu Chu Rocket (at least singly player mode). I also liked Lemmings although I never played it that much. Couldn't much get into Columns.

[noiseredux]

Super Puzzle Fighter rules. Hard.

[the7k]

Magical Drop, Panel De Pon and Puyo Puyo spring to mind.

[chuckbanzai]

You really should look into the DS, it has some of the most addictive puzzle games there are.
Mr. Driller
Meteos
Planet Puzzle League (Tetris Attack)
The Professor Layton Series
Picross DS
Picross 3D

Not to mention cool hybrid games like Henry Hatsworth

and with most of those games having download play you can play some up to 8 players with only one person having the cartridge.

[sevin0seven]

Zoo Keeper
Dr. Mario

[noiseredux]

Puyo Puyo spring to mind.

Dr. Robotnik's Mean Bean Machine IS Puyo Puyo.

[noiseredux]

Dr. Mario is great, especially for 2Player action. What's nice (and a lot of 2Player puzzlers offer something similar) is that you can set handicap levels for each player to sort of even-out the playing field. That makes it fun for players of various skill to jump in and play together.

[CRTGAMER]

Magical Drop, Panel De Pon and Puyo Puyo spring to mind.

These are good ones. Throw in Neo Geo Money Puzzle Exchanger too.

[noiseredux]

Bust-A-Move(s)

[YoshiEgg25]

Planet Puzzle League (Tetris Attack)

I was going to suggest the N64/GBC versions of this game, Pokemon Puzzle League and Pokemon Puzzle Challenge. Two very addictive games, one with awesome portability and both with the awesomeness of Pokemon.

Seriously, get at least one of those three, you won't regret it.