I had some trouble with this yesterday when I got my Galaxy S.
It pulled in the 300+ 'contacts' that I seemed to have in GMail. This basically includes everyone I've ever emailed...
In the end I just pruned everything way down. I deleted and merged contacts like mad so that only people I was bothered about were included. Now down to ~50 (that's a bit sad really isn't it :/ ).
There is a 'only show contacts with phone numbers' filter too. That might be useful.