I had a similar issue with my brother-in-laws house. It was old and poorly constructed. The ceiling was sagging badly in the middle of the living room, it was almost 3" lower in the middle than the walls!!! Turned out that the joists were terribly over-spanned...like 20' 2x4s. Earlier, he and his wife, not knowing better used the attic space as storage. Then he added a layer of sheetrock. I ended up tearing out the ceiling joists completely and replace with 2x8s. (there were no trusses). But we did some tie-ins to the rafters to support the roof. Needless to say this was a major patch job to make the house last a bit longer for them. The house wasn't worth major repairs, in reality it's a tear down.
Sorry for such a long explanation, but the bottom line is be sure your ceiling joist/truss/attic structure is solid before making more cosmetic repairs.
I like Dmoore's suggestion. His timeline is for professionals who are good at it...probably a crew as well, not just a single DIY'er! Still, I think his approach is solid: Get that old stuff outta there and evaluate the structure. Maybe add insulation if needed at the same time.
You'll want to be sure you're screwing the sheetrock to the joists, not just lathe.