I ran into something similar a little while ago, but I apologise if this is a rather vague answer.
I believe the root of the problem lay in choice of service/admin accounts for the shared services site.
First I created a new shared services provider. Central Administration – Shared Services Administration – New SSP. Make sure you follow Microsoft’s advice on choosing accounts!
I used the opportunity immeadiately after creation to go into the SSP admin and set up things like profile and account import. It’s also worth setting up audiences here because the navigation audiences don’t seem to like using AD groups.
Then back to the Shared Services Admin page and change the associations for the existing sites.
Hope this helps.