I've come up with an alternative for the dice system that is much better at handling modifiers! However, it would slow down combat, and that's not something one should underestimate. In any event, I'm going to share it here so I don't forget it, and also because the more options I have, the better off I will be.
The idea is simple - skills still dictate how many dice you have. However, all dice and all characters have the same success range, 9-12, with 12 being the magic re-roll.
Ability scores will affect successes like this - your ability score, and any relevant modifiers, will be a pool of points that you can assign to dice in your roll to make failures successes, and make successes 12s which grant you an extra die.
The way this would work is ... say someone with two skill ranks rolled 4 dice, and only got a 9, an 8, a 7 and a 6. If his strength were 3, he could change that 9 into a 12 and roll an extra die, or he could change the 8 and the 7 both into 9s and gain two more successes.
To help make this balanced, a character also cannot put more points into a single die than his base ability score. If a character has positive modifiers that increase the size of his point pool above his base ability score, he can't put them all into a single die.
Again, while I really like this idea, the prospect of how much it might slow down the game is troublesome, so I'm going to continue to think on other possible alternatives in the meantime.