The two major factors here are how many zones (and how many records in those zones) you are maintaining on the servers, and how many queries you are expecting to receive for the information. Without a measure of the sort of load you expect the name server(s) to carry we can't say much as to whether a given spec will be suitable to cover the need.
A good ball-park gauge for the number of requests if you are only hosting web services is the maximum number of unique visitors per TTL period (so if your time-to-live values are 60 minutes and you get 600 unique visitors in some hours then 10 reqs/min is probably a reasonable estimate or what you need to support). Double that a few times to account for small bursts of extra traffic.
Unless you are running a very high traffic operation or managing quite a few zones, the sort of spec that you linked too should be more than sufficient assuming that you are just running
bind or similar (and
sshd for remote maintenance, of course) on a basic OS install (i.e. no other major services like apache and no X or other such).
You need to look for reviews of the services before ordering, paying particular attention to what people say about network latency and CPU sharing - high latency or massively over-sold CPU resource will result in bad DNS performance.
Also note, if you haven't already, that you should have at least two DNS servers and that they should be both topologically and geographically separate (different provider, different network, different location).