I have installed several using sps+wss...
verify you have connectivity between project Web/Session server and sharepoint admin port (like https://my.portal.com:2733)
also verify sites path is http(s)://portal.foo/sites - do not include a / after the sites
verify project server is using correct AD account to add sharepoint sites, must be portal/wss admin.
on project server, run C:\Program Files\Microsoft Office Project Server 2003\BIN\1033\pscomplus.exe, fill in the blanks with valid usernames and password...