Thanks! I do appreciate your assistance.
My permalink is set to the "day and name," of http://www.sample.com/2008/03/31/sample-post/.
With regards to the index.php, it is not in my permalinks, I had a 301 redirect in my .htaccess and have since removed it.
Yes my home page is set to latest post in both my theme and in /Setting/Reading
Despite the above, I am still getting the 404 error messages. If you were to, say search for the word "Obama," and stroll to the bottom of the page the result will return pages 1 - 371.
If you click on any of the page #'s you get a 404 error, as an example - http://www.chocolatecity.cc/page/2/?s=obama.