REST doesn't have a recommended date format. Really it boils down to what works best for your end user and your system. Personally, I would want to stick to a standard like you have for ISO 8601 (url encoded).
If not having ugly URI is a concern (e.g. not including the url encoded version of :
, -
,
in you URI) and (human) addressability is not as important, you could also consider epoch time (e.g. http://example.com/start/1331162374
). The URL looks a little cleaner, but you certainly lose readability.
The /2012/03/07
is another format you see a lot. You could expand upon that I suppose. If you go this route, just make sure you're either always in GMT time (and make that clear in your documentation) or you might also want to include some sort of timezone indicator.
Ultimately it boils down to what works for your API and your end user. Your API should work for you, not you for it ;-).