Never mind, I found the problem. My hosting company is running PHP over CGI, I had to set the .htaccess Basic Authentication Mode setting to true under the admin panel and create the .htaccess and password file.
FYI, if any one is running into this problem check with your web hosting company to verify if they are running CGI as a module or over PHP.
Any one with Go Daddy hosting, they are running PHP over CGI.
Hope this helps someone out.