Has anyone done some extensive automation with Selenium and a Dojo-heavy web app? I'm looking for any issues or problem that you might have run into or issues related directly to the combination of Selenium and Dojo.
I've used Selenium extensively with a bunch of different web apps, including a few on Dojo. You should be fine. One practice I would recommend is to make sure all the components you'll be testing (both UI controls you'll be driving, as well as text components you'll be reading for testing) have ID tags set. Selenium has a bunch of elegant selectors to get at the elements you need, but selection by ID is still the best. The other methods can be more brittle.
I've had some challenging experiences with Selenium RC not being as compatible with my code as Selenium IDE, to the point that I stopped using Selenium RC. And in case you are not super familiar with Selenium, you should be aware that it doesn't natively support some (IMO) pretty fundamental features like flow control and includes; but there are user extensions to the framework that allow this. I'd also recommend taking a look at Watir which I now generally prefer over Selenium because it exposes the full power/flexibility of a first class language (Ruby).