May is our normal time to visit, and we've had no trouble booking inside seven months. In 2006, we booked an OKW 1 BR for 5/14-19 at 5 months. In 2007, we went 4/29 - 5/4 and booked a BCV studio at about 5 months. This year we went 5/18 - 5/23 and booked an SSR 1 BR at 4 1/2 months. May is a great time to visit - crowds are not bad, and the Epcot Flower and Garden festival is happening.
October would be more difficult if you wanted to stay at one of the Epcot resorts (BWV or BCV) because of the Food and Wine Festival.
We haven't visited in October, but we've gone in mid-November, booking OKW at 5 months.
The only time that is really tough everywhere is between Thanksgiving and New Years -- you really need to book those trips right at 11 months to get what you want.