I've been working on this idea for 5-6 years, and I think it has great potential for reallocating water while respecting the rights of existing users. It just came out in the Journal of Environmental Management.
Abstract: This paper proposes a novel mechanism for reallocating temporary water flows or permanent water rights. The All-in-Auction (AiA) increases efficiency and social welfare by reallocating water without harming water rights holders. AiAs can be used to allocate variable or diminished flows among traditional or new uses. AiAs are appropriate for use within larger organizations that distribute water among members, e.g., irrigation districts or wholesale water agencies. Members would decide when and how to use AiAs, i.e., when transaction costs are high, environmental constraints are binding, or allocation to outsiders is desired. Experimental sessions show that an AiA reallocates more units with no less efficiency that traditional two-sided auctions.
Those of you with an academic subscription can download it here. Those of you without can download my author's copy [pdf]
Addendum: I have made several different presentations of this idea for people who do not like reading academic papers. You can watch this video demonstrating the AiA, look at the the powerpoint version, listen to my lecture, or read a popular version in Solutions Journal.
You can also use these instructions [pdf] to run a demonstration of the AiA to allocate water in shortage or choose where to flood when there's too much water :)
Addendum 2: "Auctions to address issues in Oklahoma" (4 min YouTube) on OSU's SunUpTV and "All-in-Auctions demonstration" (45 min video; 72 min MP3) at the Natural Resource Ecology and Management Seminar, OSU