Perhaps an N by a username on the recent changes page can denote a new username: thus helping people figure out anons who log in for a one-shot go at things. -Stevertigo
Check the link color. If it's a new user, the user page and/or talk page link is likely to be red (non-existent). We should store the user creation date in the user table and provide that information on the user page, though.