I'm assuming you mean 35*C unless you are using phase change, but regardless, either is probably okay to start overclocking with...my idles are high at 38-45, but I haven't tried overclocking yet...at stock speeds my load temps are falling between 60-65, and those are fine...
Start overclocking slowly, of course, and prepare yourself to up your speeds in small increments, running burn tests...your temps are fine to start with, a little higher than what others seem to have, but still safe...