Prime example of people to be educated in their investments. Not everyone has to be a mechanic and I am not giving you a hard time, but really, a diff fluid change is about as easy as filling your gas tank.
Here is a quick how to that would have saved you 250 bucks and more importantly given you piece of mind.
http://www.clubxterra.org/forums/showthread.php?t=4847&page=18IMO there are very few dealerships that dont try to screw you, I have yet to find one. All of the Nissan places around here have said oh you need this and oh you need that. Last one around here told my friend she needed a timing belt change at 60k miles... If you want something done right, find people you trust or learn to do it yourself.
That being said, i know it sucks, and im sorry that you got screwed. I doubt you will be able to prove anything in your case unless they gave you the old parts (rear diff seal) and have a 3rd party verify that it was indeed blown from overfilling. ALWAYS ask for old parts no matter what they are. A buddy of mine sent his X to have the sparks changed, when he asked for them, they were scambling to "find the sixth one", turns out they only did 5 and left the 6th. I would have loved to have been a fly on the wall to hear that one... :-)
Moral is its a gamble at the dealerships. I wish it didnt have to be, bc i sure as hell dont have time to do some of the stuff my X needs, but the alternative is it gets done right, the first time.