Deontology focuses on rules, while virtue ethics focuses on virtues. Both moral philosophies seem quite similar. What advantages does virtue ethics provide?
Deontology focuses on the rules, or the universal norms. A person is said to be morally right if he conforms to these rules. For example, given a choice, a person is morally right if he abstains from killing a person, even if killing that person could bring about greater benefits.
The fundamental difference is that for virtue ethics, you can say someone is morally right only if his actions express a certain virtue. For example, a man who helps an old lady cross the road has the virtue of kindness. In contrast, lying and cowardice are blameworthy since they depart from virtues like honesty and courage.
There are no absolute rights and wrongs in philosophy. However, here you may want to argue about which is the best way to go about consigning blame or blamelessness to actions/agents in different situations. Virtue ethics can perhaps provide a set of guidelines as to what to do and what not to do. For example, if by not lying you show that you are trustworthy, by virtue you are seen as morally right and thus praiseworthy. Similarly a deontologist would say that you did the right thing since you obeyed moral norms.
However, a scenario could discern between a deontologist and virtue ethicist: a child falls into deep sea- person A jumps in to save her, disregarding the danger of the high waves. Person B decides not to make the jump, given that he might risk dying. Both the deontologist and virtue ethicist would praise person A for doing the right thing morally, furthermore he is also seen as courageous. However, person B was wrong since he just stood by and weakened his claim to virtue by displaying cowardice.
In a similar scenario, what if there was a reward of a million dollars? We can predict that person B will likely jump in to save the child, since the reward far outweighs the cost. In the deontologist books, he does the right thing by this action alone. On the contrary, a virtue ethicist would say that one action is not enough to determine that he is a virtuous person. In essence, he is still a coward inside.
The fundamental "virtue" of virtue ethics over deontological ethics -- for which Lok123's answer provides a useful case-based analysis -- is that the former centers on what actually constitutes and underpins morality on the essential level (i.e. psychic and psychological) while the latter centers on an arguably "blind" commitment to certain abstract rules that due to their said abstract nature are incapable of accounting for indefinite contextual and relative factors that determine what is truly right in a particular situation.
In other words, virtue ethics focuses on the very essential aspect of ethics from which morally consistent decisions and results can emanate with respect to any given situation (a feature that is evidence of a truly "universal" ethics), whereas deontological ethics in its very quest for universal morality fails because of ignoring or dismissing what truly constitutes universal ethics: not abstract mental rules but actual psychic qualities, i.e. the ontological principles of ethics.
Consequently as pedagogical implications, in the school of virtue ethics, morality is materialized not merely by popularization of abstract moral maxims that are disconnected from an ontological basis and disregard benefits for the individual itself (that are also key in actually motivating morality), but more importantly by following codes of discipline and conduct that lead to cultivation of psychic qualities that basically makeup the whole character of the individual and consequently determine the moral nature of his actions consistent with the greater good in any given situation.
This contemplation may explain why under the deontological and quality-lacking morality of the modern world (and consequently the colonized traditional world in as much as the modern cultural norms have made inroads) despite all the official ethical rhetoric and pretensions, societies are suffering from all sorts of moral ills and most politicians have become basically lying crooks while putting on moral pretensions of saints!
In real terms there is no difference between the two as both are drawn from the (deeply flawed) "moral intuition" approach. Both the concepts of what is virtuous and the rules on which any deontological ethics is based both come from the same source, our "moral intuition". Thus differences between them do not result from differences in the approach, but differences in the moral intuition guiding them. To take the example given in Loki's answer. The person jumping in to save the child for a million dollars would not be judged to have done the right thing by a deontological ethics which ruled against action obviously motivated by greed. In Kantian terms we would not want a rule which encouraged people to be motivated by greed regardless of the outcome and would rule against it morally. This is basically an expression of the fact that we think altruism is a virtue.
This is not to say virtue ethics has the greater claim to authenticity as the same could be said the other way round. Why do we consider altruism a virtue? Possibly because if everyone were altruistic that would make a rule which we would be glad to make universal.
This is essentially why I mentioned in the first paragraph that both approaches are deeply flawed. Neither is capable of saying anything new, both are descriptions of how we act, not instructions on how to act. Descriptions of how we act should be derived from properly controlled scientific investigation, not by philosophical speculation.