ErrMsg "There is insufficient space to index your content."

After I had added a few MP3 files (about 70 songs) and a playlist, the player stuck on indexing after disconnecting it from the PC. After 4 hours the progress bar was still at the same position where it was like 1 minute after the reboot so I do assume it stuck. I'm using Windows Explorer to add music - never used any media player to sync.
So I turned it off and after firing it up again it just comes up with the Rio-log before it resets. It will stay in this loop until I power it off or I connect it to the PC again.
I did a reset, formated the disk (quick and full), re-installed the firmware (1.43) and got all kind of strange behaviors. The most notable thing was the message I got two times after I falttend the device and restarted it (there were no files on the device):

"Remove tracks"
"There is insufficient space to index your content."
"Delete some tracks?" (Yes/No)
-> Yes
"Chose content to delete?" (Oldest/Newest/Cancel)
-> Oldest/Newest
"Connect to PC and delete some content manually."

Now I am in the state where I can add MP3s and playlists but it will not even attempt to index them. It will notice that some diskspace is used but it will always show "no tracks" as well as "0 tracks, 0 playlists" under "About".
Does anybody know how to get this thingy back on indexing?

TIA
.olaf