There are 3 main reasons to want to exchange your DVR/STB:
1.) Your current DVR/STB is malfunctioning.
In this case, you can get a free replacement. However, it might not be an upgrade.
2.) You have a model 6200 or 6416 and cannot tune to certain HD channels included in your subscription package.
In this case, you can get a free upgrade. But while a replacement DVR will most likely have a 500GB drive, it is not required to.
3.) You just want a DVR with a 500GB drive.
In this case you will have to pay the $40 upgrade fee.
I've heard that it is possible to go to your local FiOS store and beg for one. But I can't promise results.