Console-wise, I haven't encountered a lot of games with good stories this gen. A few story-driven games that put the story as their main focus suffer from storytelling, or being poorly-written (MGS4 and Heavy Rain come to mind). Anyways, these are the ones I've enjoyed this gen. I'll also include handheld games and last gen games (PS2 mostly).
Folklore - Has a slow start, but it has a fantastic story. Very suspenseful and having two different perspectives was pretty interesting. Folklore is, imo, one of the few games that uses the sixaxis feature very well. The only downside to this game is that it's repetive; you have to go through the same dungeons and fight the same bosses twice.
Batman: Arkham Asylum - I know what you're thinking, "you're putting a superhero game for a good story suggestion?" On the surface, the plot looks simple: Joker takes over the asylum and you (Batman) have to stop him. The thing that makes the narrative solid in this game is the characters; the characters drive the game. My favorite sections have to be with Scarecrow, since you dig within Batman's past, and it has a creepy but amazing atmosphere. It also has a lot of riddles and things to find, and you can find out some of the character's backstory through patient tapes. Gameplay is good, but the boss battles are mostly disappointing.
Uncharted 2: Among Thieves - U2 delivers a true cinematic experience unlike MGS4.; it seemlessly blends gameplay and cutscenes. The story is decent, but it excels at storytelling.
Mass Effect 2 - Wasn't that big of a fan of the first one; I liked the story, but the gameplay was so-so. I haven't finished ME2 yet (only played for about 10 hrs.), but so far, the story has been very good, and the gameplay is top-notch.
Vagrant Story - Not sure how you feel about downloable PSone classics, but you defintely try this out. The story and characters are unparalleled. Matsuno is a God; every game he directs is exceptional. VS does have a steep learning curve and can be a frustrating though.
Ace Attorney: Phoenix Wright - I'm normally not a fan of this type of game, but the cases/stories in this game were very good and, for the lack of a better word, smart. Gameplay involves finding evidence at the crime scene, and then examing the witnesses and presenting the evidence you found at trial.
Shin Megami Tensei: Devil Survivor - This is my favorite handheld game of this gen, and most of it has to do with the story. It's incredible, dark, immersive, etc. My favorite thing about DS is the branching paths; the actions you take at battle or cutscenes alters the game's ending and your alignment. There's several endings, so this game has a lot of replay value.
Shin Megami Tensei: Persona 3 Portable - The persona games are some of the best JRPGs in recent years. Persona 3 has a solid cast with great character development, and each character plays a vital role in the story or has a strong motivation for being there (except for maybe the dog). The setting is very cool/unique (it's set in a modern city of Japan) combined with a nice, dark atmosphere. Between Persona 3 FES and Persona 3 Portable, you have to decide what you want. P3P has the better battle system and is easier, but it doesn't contain the expansion pack (the story after Persona 3) and doesn't have the animated cutscenes.
Tactics Ogre: Let Us Cling Together - I consider this to be the greatest SRPG of all time. The story is pretty awesome; in fact, I believe every Matsuno game have an amazing plot, but I consider this one his greatest as it has choices and consequences. II'd also recommend FF: Tactics.
Yakuza - Since you liked Yakuza 3, I would recommend the first Yakuza game. The story in this game is amazing; one of the best I've seen in a videogame. There is some bad voice acting though. Imo, Yakuza 3 has the weakest story in the series, so you should give Yakuza 2 a go too.
Digital Devil Saga - Another great JRPG from the SMT series; I consider this one, along with Devil Survivor, to be the best in the series in terms of story. Unlike Devil Survivor, DDS has only one ending and no branching paths. It has a lot of religion/mythological references which makes the plot more interesting. The story is about six tribes in a war; the winner of the war gets to go to nirvana.
Persona 4 - It has a very slow start and poor pacing, but despite these flaws, the story is very good. Like Batman, the characters drive the game. It does a great job developing and making you love each character. A lot of the magic from this game derives from character interaction. The story is about murders/bodies appearing after a fog. You have to save people and find out who the killer is. Great story with lots of twists and turns. Personally, I think P3 has the better plot & characters.
The Witcher - I suggest you continue with The Witcher. It's one of my favorite games this gen. I didn't like it at first, but I gave it a chance and found myself hooked. I liked the choices/paths it offered. Are you playing the Enhanced Edition btw?
Grim Fandango - A couple of us at Gamespot were discussing which game had the best story, and the majority of choose Grim Fandango. I recently played it since many were praising it, and yeah, it has a solid story. Excellent game.