I've read that this is being caused by the following bug-like behaviour.
The map generator creates a map and all the desert tiles along rivers are floodplains. Then the civilizations are placed on the map. The area around the settler of all of the civilizations is improved so that every civilization starts in good terrain. Sometimes this includes adding rivers to the map. If those rivers happen to pass through desert tiles, then those tiles are not upgraded to floodplain tiles.
Is the river in question somewhere on its route close (within 5-6 tiles) to a capital?
By the way, I've read this. I don't know if it's true. I do know that I've seen deserts along rivers in earlier versions of civ4, pre-BTS. In all cases they were next to rivers that were close to the capital or were caused by the destruction of a city that was founded on top of a floodplain tile. (Floodplains are overlays and overlays are removed by settling a city, just like forests and jungles.)
The question is, should the algorithm that improves the land around capitals and thus sometimes places rivers also upgrade deserts to floodplains? It would then upgrade the terrain a lot further than by just adding the river. From a game consistency point of view, I would say yes (deserts next to rivers are floodplains everywhere). From a balancing starting positions point of view, I would say, I'm not sure.
I would personally prefer if the starting position algorithm would add the floodplain overlay to deserts next to rivers. I would also prefer if the floodplain overlay was added again when a floodplain city was destroyed. I like consistency in a game.
edit: Bindamel was faster.