Hi Brett: Lots of questions. I'll try to hit them all. I prefer to answer questions on the HUBB because then other folks can take advantage of the info later on. But if you need my email contact info, let me know.
1. Naushki is a small Russian town on the rail line. The closest Russian town to the border is Kyakhta. You can make it from the border to UB (Ulaanbaatar) in 5-6 hours depending on how hard you ride. The road is paved all the way, though the paving is of uneven quality.
There is a border crossing at the top of Huvsgul Lake, but it is only open to Mongolians and Russians. A few large foreign tour groups have managed to cross there, but only by obtaining prior permission ($$) from the Russian and Mongolian Foreign Ministries.
2. GPS/Maps: I think with the Garmin 60 you should be able to load the Garmin WorldMap base map for Mongolia from the WorldMap CD-ROM. That is by far the best GPS map for Mongolia. I can fit all of Mongolia into the memory of my Garmin GPS V, so you should have no problem with a newer model.
There are not any topo maps of Mongolia. There are some detailed Russian military maps that you can sometimes find, but a set of those for your route would be about 10 pounds of paper (and you'll need to be able to read Russian). Your best bet is to get to UB and buy the "Mongolia Road Map" and the "Mongolia Atlas." Those two are the best driving maps for Mongolia. They have distances between towns and gas stations marked. You can buy them several places, but I recommend Xanadu Books, which is the best English language bookstore in the country. It's also next door to Millie's Espresso, which has the best coffee in the country. Convenient! Millie's is in the LP guidebook. They are about 50 meters west of the front gate of the Chojin Lama Museum in downtown UB.
3. There is a Kazakh Embassy in UB. I don't know any foreigners who have gotten visas there, but they do issue visas, so they should be able to help you. I have no idea what you need to get a Kazakh visa, though. The Embassy is located in the "Diplomatic Compound" about 50 meters NE of the Lenin Museum/Freedom Square, entrance #2. The phone number is 976-11-312-240; fax: 976-11-312-204.
4. Places to stay: There are many guesthouses in UB. Most can provide safe bike parking, usually by locking the bike in a shipping container at night. The UB Guesthouse (http://www.ubguest.com
) is popular. Some riders have also stayed at the Khongor Guesthouse (http://www.mandarinmedia.com/projects/khongor/)
5. Routes west: There are basically two: North and south, divided by the Khangai Mountain range. The northern route has rougher tracks, but is prettier (greener) scenery and you can stop at Huvsgul Lake on the way west. The southern route has smoother tracks, but less to see (lots of wide open Gobi).
There are some variations on how you can do the routes, but here are the main tracks I recommend:
Northern route: UB-Kharkhorin-Tsetserleg-Murun-Huvsgul-Murun-Uvs-Ulgii-western border
OR UB-Erdenet-Murun, etc.
Southern route: UB-Kharkhorin-Arvaikheer-Bayankhongor-Altai-Khovd-Ulgii-western border.
No matter which way you go, it will be almost entirely on dirt tracks with no signs. Whether you are looking for rough riding or not, you're going to get it.
A 400 km range will be more than enough, though you should top off in every town that has a decent gas station. Most of the fuel outside of UB and the main cities is only 76. I haven't heard of anyone having big problems with the 76, though to be safe you probably shouldn't try to redline it on the low octane stuff.
As for riding time, you can do the southern route in 3-4 long, hard riding days, and the northern route in 5-6 of the same type days. If you allow a week for the southern route and closer to two weeks for the northern route that will give you time to relax and look around a bit and you won't have to ride more than 3-4 hours a day unless you want to.
Let me know if you need more info.