Chris, this is just my opinion, but you need at least a 400mm lens if you want to go birding, and that costs. Expect to spend close to four figures if you want decent performance at these focal lengths.
I'm a Canon shooter and I'm thinking in terms of Canon lenses and then translating into Nikon equivalents, but my first recommendation would probably be the Nikon 80-400 VR, particularly if your interest is more in perched/standing birds, rather than birds in flight. The only big drawback with the 80-400 is that it's not AF-S, and some folks perceive the AF speed to be slow. But then, when you're shooting BiF, any autofocus speed seems slow. :) If, however, you're happy with the reach of the Tamron 70-300 and you just want better quality, then upgrading to the Nikkor 70-300 VR might be an option.
If you can't afford the 80-400VR, there are the Sigma alternatives, like the 120-400 OS HSM and 150-500 OS HSM, and they're great value. But. I once read
a lensrental piece where they said both of those lenses were in their "Hall of Shame" for a 45% failure rate. They may have gotten a bad batch, and rentals are obviously going to see a lot more (ab)use than the average, but it's still something to consider.
And, on top of that, as a Canon shooter, I've seen
a review/test on the juzanature.com site, which compared the 120-400 OS, 150-500 OS, the old Sigma 50-500 (aka "the Bigma") and the Canon 100-400L, and of the three Sigmas, the Bigma was actually the best performer. The only trouble is that the Bigma is also a beast to handhold. Once you go past 400mm, you'll probably want to be shooting with a tripod or at least a monopod.
In terms of prime vs. zoom for supertele--it depends on the usage. A prime is typically going to take teleconverters better and autofocus faster than a zoom. But I seriously curse my 400/5.6L USM prime when I'm at the zoo (and I run backwards a lot). A 400mm prime can be very limiting, unless
everything you want to shoot is too far away, anyways. Which pretty much sums up birding photography. :)
One other small note. With the Tamron, if you haven't, try stopping it down to f/8 or f/11 and see if that helps you with sharpness. A lot of the lower-cost 70-300s have lousy wide-open performance, but can improve when stopped down.