Access Denied - Error message when we access https://xxxxxxxx/PWA - Project Web Access

Initially users on the client machines were seeing "Access denied" message when they try to browse to https://xxxxxxxx/PWA.

When we try to access the PWA on the Project server 2007 server, we saw the same behavior.
No matter what account we use to access the PWA, we see access denied, we also tried the SharePoint service account " System Account" but no luck.

When we get the access denied message, simultaneously we saw that the following event being logged in the application logs on the project server.

Apparently we saw this Event ID getting logged frequently

Event Type: Error
Event Source: Office SharePoint Server
Event Category: Project Server
General
Event ID: 6058
Date: xxxxxxxxxxx
Time: xxxxxxxxxxx
User: N/A
Computer: (computer name)Description:

Failed to get language information for Project Server (http address)

We implemented KB article - https://support.microsoft.com/kb/934838, ALL the command in this KB completed successfully.We did a re boot of both the SharePoint servers in farm. Still the problem was occurring.We also restarted the 2 PRJ services, SQL service, still no luck.  Eventually  we saw that the SSP links like - the search settings, search administration , user profile properties links were also not working.

ERROR- An error has occurred while accessing the SQL Server database or the Office SharePoint Server Search service. If this is the first time you have seen this message, try again later. If this problem persists, contact your administrator.

We implemented the steps in - https://support.microsoft.com/?id=962928. "You cannot browse to an SSL-secured Office SharePoint Server 2007 site or to the Search Settings page for a Shared Services Provider".

Installed- KB- 959209, Re booted the server, All the links started working in SSP and the PWA site also was accessible.