Let me try to help:
What you have is an .avi file coded obviously as MPEG4 Part 2/ASP (the normal .avi stuff), NOT some kind of video file in an MPEG4 container (.mp4 file), right?
This is happening to me, too. Plays just fine on the PC, is served just fine to the box, but the box says "Invalid Format". My guess at this point is that the box, at least in part, evaluates some combination of mime type, file extension and that fourCC code. For video encoded with XVID, fourCC code XVID seems to work just fine. I am having trouble with video encoded with XVID, but with a fourCC code of DX50 (from memory, here, I might have a letter wrong). I am unfamiliar with the subtleties of it all, but I am pretty confident the source of my files is ASP, so I will give a shot to just changing the fourCC code to XVID and see what happens. If it works, maybe D-Link might want to consider adding that DX50 fourCC code as a supported value. Maybe there is more to it that escapes me at the moment. Doesn't the manual refer to the box as Divx 5 and 6 certified? I know XVID is a parallel effort to Divx, but still.
To your question, GSpot is a good video information utility. I seem to have come across MediaInfo at some point for the same purpose. For the fourCC editor, there is that .avi tag editor (abcAVI, or something) and FouCC Changer. Google is you friend to locate it all. Best of luck, and report your findings. I would love for this forum to become "the place to go" for anything on the DSM-510, and this will only get as good as our collective contributions.