Azure Dreams on either the Playstation or the Game Boy Color - You scale a 30 floor, randomly-generated monster tower collecting weapons. You don't capture the monsters the way you do in Pokemon, though - you have to find an egg in the tower, escape the tower with it, and hatch it in your house. However, the combat isn't random battles, but rather a cross between turn based and real time. The PSX version also has a town building mechanic, while the GBC version has a lot more monsters to obtain and a 99 floor basement that unlocks after scaling the tower twice (you have to have your starting monster when you do it the second time, or it won't unlock).
Magi Nation on the Game Boy Color - This was actually based on a card game, but it's pretty similar to Pokemon what with you battling monsters, forging rings to summon them, and battling other people with monsters. I thought it was okay, but it's kind of slow and unfinished, what with some monsters being unobtainable without a hacking device and it's actually possible to run out of keys and get stuck in two dungeons. Also, the steps to obtaining the strongest monster are so bonkers you have to wonder how the guy who wrote the FAQ at GameFAQs figured it out (for one of the steps, you're given the clue after your window of opportunity to actually do it).
Dragon Warrior Monsters has been mentioned, too.