In the specific cases you mention - the First Posts and Late Answers review queues - there are strict definitions of "new user".
In general, there's no strict definition. Different people use the term "new user" in different ways, according to their own reputation and time on the site. Some people would see me as a new user, since I've only been here since 2014; others probably see me as one of the mainstays of the site. It's all subjective. There are only two possible general definitions I can think of:
users with less than 10 reputation: according to the help centre, one gets "new user restrictions" removed at this point (though I still think of some users with >1k rep as being new)
users who've been around for less than 45 days: this is the definition used by the new users tab in the user list (thanks to @anaranjada for reminding me of this)
Would I be considered a new user?
I would say no. You have over 5000 rep, and you've been a member of this site for longer than two of the moderators - you're no noob :-)