One recent example: Two Souls has one of the best story and characters but is getting mixed reviews because it's pretty much a movie that you paid $60 for and that runs for 8 too many hours. The few parts where you get too play are not that great apparently.
But that does not mean story is not important.
One of my favorite game of all time is Another World. There was a story, it was simple, it's mostly told through gameplay (some cutscenes, but never longer than a few seconds), without the need of dialog. The action was great and rarely repetitive. Great graphic for the time (still holds up today), great atmosphere, many innovations, and all this made by one single guy, living at his parent's
A great inspiration for me !