Several people have had this problem, including myself.
Inside my Sansa E260...
.rockbox/doom/rockdoom.wad, doom2.wad, ultimate.wad, tnt.wad, plutonia.wad
rockdoom.wad clearly exists. I updated Rockbox two minutes ago. And the plugin still returns a "Missing base wad" error.
What's up?