Have you owned this car since new or is it used? Maybe the previous owner adjusted the clutch cable as the clutch wore, and then sold it to you like this. And now the new clutch is in and there is too much slack in the cable adjustment ( if cable and not hydraulic). And so when you push the pedal, maybe the pressure plate cant go far enough out from the flywheel (pedal not pulling pressure plate out far enough) and disc and makes it hard to shift?
New clutch or no new clutch, if anything it oughta shift the exact same or BETTEr than before the new clutch and not worse! If you had it done at a shop, i bet the sloppy mechanic did not even test drive it.
Try adjusting the clutch yourself, it is not too hard. BUT remember the trick is:
You must leave at least an inch or two of slack at the pedal. The factory manual says how much slack. This is important Because - If the clutch adjustment is too far and too tight, then the pressure plate will be held away from the disc and flywheel a little bit, even when the clutch is out. So this will cause the clutch to wear out fast and that you surely do not want.
If you had it done, take it back and try to get them to adjust it for you. If you did it yourself, check the Camry manuals for the detail info -
http://oregonstate.edu/~tongt/camry/