I also have a 1996 Maxima SE and have been having the same problem. I had the speed sensor replaced and within two days, light back on. The shop at the dealer (Jones in Bel Air, MD) refused to clear the code and wanted me to replace the speedometer for $650 (they don't print the error code on the receipt). I took it somewhere else and the mechanic told me it was the speed sensor again but he did clear the code for me so I could see if the light would come back on. I really don't think it's the speed sensor because mine has been replaced twice in the last two years (I forgot I had it replaced slightly over a year ago - code P0500 found). I also don't believe it's the speedometer. I started looking around and found this info:
http://autorepair.about.com/library/faqs/bl035e.htmIf my light comes on again, I will ask the mechanic (not at the dealer) to check these wires and replace if possible. I'm not handy with cars so can't do it myself. Other than this annoying problem, my car runs great!