I was torn between using PS and CC3 to create my large scale map but was leaning towards PS. Next I determined that a 36" x 36", 300 dpi drawing is 10,800 x 10,800 pixels. I have a pretty decent notebook with lots of memory and a kick ass video card. Still, PS was huffing and puffing enough for me to see that wasn't the way to go. (largely in part to it being v7 I'm sure).
I used my old map as a background in CC3 so I could trace polygons over the png image and get the main features copied over. Got a good start already and no more fighting huge file sizes. The resolution-independence is a nice bonus.