Yup, you have to call and make sure you get a good agent that will search many multipe dates for you and not some lazy agent that says they have to stop after 3 date searches. (Delta has decided not to make most partner award availablity searchable online for some strange reason after they merged with NWA, forcing you to call and spend much time on the phone)
Keep in mind you can only redeem into business class...not into first class.
Also, depending on what route you are looking for, look out for the A380..they have 94! business seats so there are often numerous award tickets available.