Completely Confused: Malware Warnings

Greetings.

I have a client site recently created that appears to of been hit by Malware. I have searched the forums for solutions and followed the recommened links. I have thoroughly scanned my system and had my web host check and scan the account files on the server but no malware or infected files have been found.

So let me explain the events:

1: Acquired new web host with WordPress installed on the account. Used default theme and all was file on front end and back end.

2: I downloaded and installed the Simple Catch theme but when I activated it, I got Malware & Phishing warning messages (screenshot of warning message) when accessing site from the front end. No problems in the backend.

3: Had everything scanned and checked. No issues found yet Malware warnings persist.

4: I deleted the Simple Catch theme folder on the server and front end warning messages stopped when using the default theme but now when I click on the back end pages to either edit Themes, Background, or Header, the same warning messages occur when they didn’t prior to installing or deleting the Simple Catch theme.

5: Had host re-scan all files and nothing is found.

6: These messages appear with Chrome and the Firefox browsers but not with Explorer.

7: I am on a PC win 7 64 bit using Shaw Cable McAfee anti-virus software.

I have created several other client sites hosted with two other companies and around 8 .wordpress.com sites and none have had this problem. So what is going on here and what needs to be done to resolve this?

Your help will be appreciated. Thanks!