Well, aside from the fact that he recruited *one* lineman for those horrible 2004 and 2005 classes...
Willingham's problem was that he tried to run a very much stripped down version of the West Coast Offense, where he took out most of the downfield passing aspect. That was OK for his time at Stanford, where outside of USC, that Pac 10 was a very weak conference, to say the least. Once he got to ND, the competition level was much higher, and a kid-friendly offense got squashed.
This isn't to say that the WCO can't work in college. Far from it, since Jim Harbaugh successfully used it at Stanford and Michigan. Harbaugh, though, ran a relatively complete WCO.
While the WCO is built around short passing plays, it still requires a QB who can sling it downfield with reliable accuracy in order to prevent teams from squatting in a short zone and zone blitzing.
It was all too predictable, especially with a triple option QB at the helm in 2002, as well as in 2003 where Carlyle Holliday started the season, and a very green Brady Quinn finished it. Heck, it was too predictable in 2004 where it was all too rare of an occasion where Quinn was allowed to throw downfield.