It wasn't that bad of a job at all compared to subfloors!
We did like Greg mentioned and opened up the inside walls. We shut the power off, since we need to move a junction box for a light switch over a few inches. We removed one stud to widen the door using a recip saw, then used the recip saw to cut the old header out to the right height. Placed a new stud into the doorway, and reconstructed the header. Hooked the junction box to the new stud. I had carefully removed the paneling, so all I had to do was cut a larger area for the door in it. Placed the paneling back up (we've got real wood paneling, so this was easily done).
After that we dry fitted the door, shimmed and leveled until it was perfect. Screwed it in, added new lock set and dead bolt and we were in business!
Now, one thing that our neighbor suggested that we do, is not trim the door out for a few days. That was a pretty good tip, because we did tweak the door to the perfect level and fit over the next few days.
Maureen
