Have you checked the ECT? Any time I see a temperature-sensitive idle, I like to check the ECT before anything else. If it were reading too warm you're going to be getting too lean of a mixture at first, which will cause difficult starting and a low rough idle. It'd take a pretty lean mix to cause a P0301, but I'd check ECT before checking plugs or wires. See www.camrystuff.com
, Generation 4, SFI (Sequential Fuel Injection) section, starting at page 48 for the ECT specs.
FWIW, the Scangauge may be able to give you the direct engine temp reading that the ECU is seeing, which would make checking the ECT dead easy...if engine temp is reading quite a bit higher than air temperature after an overnight cold soak, you've found your problem child.