Did you check to make sure the proper SMS entries exist in AD? Open AD Users and Computers. Drill down to <DomainName> | System | System Management. You may have to go to View | Advanced Features in order to see the System container. Just make sure you see MP and SLP entries.
If you do not see any entries, chances are your SMS servers do not have rights to the System Management container. If you are running Advanced Security, you must give the SMS machine accounts access to this container. If you are using standard security, then you have to give the service account access. You can also view the hman.log file on the SMS server to get details.