@ Sanket:
Regardless of how many states you lived in India, there is only ONE PCC certificate. The Agent is correct. The address where you lived/visited in India AFTER you landed in Canada is important. I think there is one other place where you mention the addresses you lived in India and how long you lived etc. Anyways, you don't have to worry about the two states where you lived. I've heard most people who dont have criminal records get it within 1 to 8 weeks. Exceptional cases get delayed for a long time. There is no such thing called PCC from each state of India.
Just a note: PCC can be obtained both thru Passport Kendra (A Central Govt. agency) for 500 Rs. or through approaching the office of the Commissioner of Police for the area where you lived. (The Commissioner should in his discretion redirect it to the local Police Station for checking for your records) My earlier post was the process only for getting it from Passport Kendra. I know this because I obtained my previous PCC while i was in India thru the Passport Kendra. One can also get it from your local Police Commissioner office for which even someone you authorize is fine and even original passport is not required. I know my friends who are here in Canada but used their dad in India (and their influence/money) to get PCC from Indian Police directly and asked them to send it via courier to Canada which they used for PR process.