What blog are they registering in and what blog are you checking the users list in? Multisite blogs don't share users unless you use a plugin that allows it.
What I meant was blogs in the same multisite network. You know, there's the main blog and then several child blogs, all in the same domain and network.
Where are you registering the new user and where are you looking at the users list? Are you registering in Blog A and looking in Blog B or are you doing blog in Blog A?