If you could abide with JRPGs, you should definitely give The Last Remnant a go. It’s not grind-heavy, the story-line is decent, the acting is alright, the gameplay is great and there’s a solid good chunk of perfectionist material in there. While the main character is something of a git, there are some truly good supporting actors. And a few very, very powerful moments in the story.
However, and this has to be said, the PC release was a vast improvement on the console, due to far better controls, less bugs and faster loading times. If you have a PC, I’d recommend getting that version.
Lost Odyssey is in the same vein, another JRPG, but the story and main character is far better developed and executed, at the price of some blowback to the gameplay.
Mass Effect is, however, the quintessential Xbox 360 RPG. If you haven’t played it, you are missing out. And the sequel (Q4 2009/Q1 2010) is shaping up very nicely.
I definitely enjoyed Overlord. While it’s quite simplistic, story-wise, compared to Fable II, it’s also a lot more simply funny. And Overlord II is coming in about three weeks. 
Dragon Age: Origins is scheduled for the fall. Definitely one to keep two eyes on, when you can spare them.
Bioshock is far more of an RPG than most people would think. Yes, the combat is FPS, and sometimes a bit twitchy, but features the best and best-told story in Xbox 360 history.
The Witcher, a very underrated RPG based on the books of Andrzej Sapkowski, was supposedly coming to the Xbox 360 in a reworked form. The project is currently on hold because of quality assurance problems; the developer, CD Projekt, is known to have issued public apologies on radio and television, in Poland, regarding the state The Witcher was in when first released on PCs back in 2007. It’s development is, as said above, currently in suspension, but the fans maintain good hopes that it will be back on track shortly.