Should I be worried if I accidentally entered my password in a username field?
The short answer is that it is very, very likely that your concatenated username and password exist on an unencrypted log somewhere that a larger group of people would conceivably have access to than the restricted logs.
You are not paranoid to change your password and should change it when this happens.
But if this happens my password would be stored in some unencrypted log somewhere, right along with my username.
Is this a reasonable concern?
Yes.
Am I being too paranoid?
It depends.
If your worry is about the password being stored, then absolutely you're not. Your password will get stored in the clear to a near certainty. Being aware of reality and current practices is not paranoia.
To worry about the damage that the leaked password can cause - hence the prompt password change - is another matter. There, you might be a bit paranoid... but then again, no, depending on your overall password policy and the kind of sites you usually visit and leak your password on.
There are two mitigating factors:
The log file will almost certainly be viewed by nobody else but administrators (if ever, if at all). They probably already have the means of both impersonating you (i.e. logging in as you, even without knowing your password) and stealing your password, even if the website ought to store it in encrypted form. Also, unless it's some wannabe-run site, administrators are actually on a fairly short leash and cannot e.g. just browse the logs for fun. There are usually first-level filters that submit a portion of the log and the reason for the alert; this mainly to reduce the time spent in checking the logs. Your single failed login shouldn't even trigger a low level alert.
I'm pretty sure, given your security consciusness, that your supersecret password is not reused on multiple sites. Therefore, even if it leaked, it would be no great mischief.
The main danger from passwords leaked on the same site they're used on is that they might supply insight, or straight access, to some other site due to password reuse. An administrator that was kept honest only by the awareness that an access on his site would be immediately tracked to him, might feel friskier towards a third party site which he doesn't administer and where he's not known.
Therefore, if I were such an admin, knowing that your password on my site is loneboat3 would probably make me try loneboat as well as loneboat0 through loneboat9 on your banking site.
And in your case I suspect this danger is negligible.
That said, I think that changing a password as soon as you feel it's been compromised is a very good habit to have no matter what.