I'd say the question is one of too many. If you think of your standard country drop-down, it would be completely unusable if it weren't for the fact that you know the name you're looking for. Auto-complete on a country is not a bad idea since users will type it correctly for the most part and get relevant names almost immediately. This would stop the really bad interaction associated with scrolling through all country names.
Another way to approach it is, if you know most users are in a couple countries, like the US and Canada, put them at the top, out of alpha order and then alpha everything else.
In terms of navigation and menu options, some people feel optimal is around 7 items, but with the current trend to megamenus and info rich sites, this is potentially outdated, going back some time. Plus, this is psychology related to short-term memorization and not scanning. We can perceive very large numbers of options. Big menus risk being a wall of text so moving toward ajax features such as auto-complete, where possible, is a good solution.
You can see more about the 7 +/- 2 options and whether it is particularly valid at http://drdobbs.com/web-development/184412300 ...