As others have said, there are two problems here:
1) The Arduino has an inefficient linear regulator on it that requires about 6.5V in to generate 5V out. Thus, you should regulate to >= 6.5V, not to 5V. (7.2V, 9V, and 12V are all easy to find parts for and would work well.)
2) Linear regulators are really inefficient when regulating high voltage drops. They have to pass all the current that the load is drawing, and burn it off as heat. Switching power converters are a lot more efficient in these cases.
You can buy a suitable power converter either at distributors like
Digi-Key ("dc dc power converters") or perhaps at hobby shops (where they will be called "UBECs" -- just make sure you get one that can deal with 36V input.)
Also,
Pololu are selling a few, which are in the same family as the ones you'll find at Digi-Key, but I don't think any of them go as high as 36V.
Finally, you can build your own step-down ("buck") converter with a switching controller IC, and a few discrete parts; typically a diode, an inductor, a few resistors, and a capacitor or two. For an easy-to-use through-hole part, try the
MC34063, which is not particularly efficient, but it can take high voltage and is robust even on breadboards.