Took me a few hours to figure this out. I actually did a reinstall of my SharePoint 2007 after it got screwed up. I reinstall Windows Server, had it join domain, logged in as a domain (added as local admin earlier). The whole installation went fine until the point I have a create a Shared Service provider, I got hit by a Access Denied error when I create a web app for both SSP and My Site.
At first I tried to login with a domain admin account but I got the same error. In the end I realize the problem is caused by SQL Server. You see problem arise when I tried to delete all SharePoint database from the database server but I left the SharePoint service account there.
In the end I uninstall SharePoint, go into SQL Server delete all databases and the account and it went smoothly.