Are you working from shape files. I have never used the tool before 5 minutes ago. I just ran it on 240 points scattered over a region in the US. I did it at 1000 and it only made 3 polygons, 10000 it made 24, and 100000 it did only 2 (one very large)
check to make sure you do not have any multipart points.
If you are using a shape file. Create a new ShapeFile based on the originals attributes and use the data loader.
If your in a database, compress the database.
What projection are you using? If you are using a small regional projection that may cause an issue if parts of the polygon go outside of it.