If you were using a pseudonym not clearly tied to any legal name you have or have had, I am not sure why people would think it odd that the pseudonym arrived all of a sudden.
I have been fairly sloppy in keeping my different pseudonyms separate, (though I personally don't have much reason to work particularly hard to keep them separate) so this might be less informative, but I've never really had an issue with people thinking it odd that a pseudonym of mine appeared suddenly. On the other hand, I haven't published much of note, so that might be part of why.
If you intend to use a pseudonym, but one which is clearly connected to your new legal name, perhaps you could introduce the pseudonym without connecting it to your new legal name, and then after a bit, once the amount of recognition and/or time that you think is appropriate has been obtained/has passed, start connecting the pseudonym to your new legal name?