Most surface-based observing systems in New Orleans failed, whether due to the instruments themselves blowing away or power going out, before the strongest winds were felt in the city. It is reasonable to assume that they felt at least category 1 from the last observation from the Lakefront observing platform -- http://www.srh.noaa.gov/data/obhistory/KNEW.html -- since at 7a CT they were at 69mph. The HRD analysis suggests only category 1 winds, available from http://www.aoml.noaa.gov/hrd/Storm_pages/katrina2005/wind.html, but note that the data is merely preliminary.

In other winds...it remains to be seen. Whether or not they were felt any stronger than that doesn't matter a lot; the wave damage with the storm was immense and the two-three weaknesses in the levee system were exploited as a result.