This is not a formal address change as yet. They just moved out temporarily, and should be back unless it is decided that the city should not be rebuild, which is unlikely. You notify USCIS only when you move. Not otherwise.
Do you notify USCIS everytime you go out of town for a few days? I hope not. So why should Katrina victins?
USCIS has been known to be unreasonable but I cannot imagine that they will prosecute some poor soul who lost his home and did not notify USCIS of it.