Inference on regression coefficients when the response variable consists of overdispersed counts is traditionally based on Wald, score and likelihood ratio tests. As the accuracy of the p-values of such tests becomes questionable in small samples, three recently developed tests are adapted to the negative binomial regression model. The non-trivial computational aspects involved in their implementation, some of which remained obscure in the literature until now, are detailed for general M-estimators. Under regularity conditions, these tests feature a relative error property with respect to the asymptotic chi-squared distribution, thus yielding highly accurate p-values even in small samples. Extensive simulations show how these new tests outperform the traditional ones in terms of actual level with comparable power. Moreover, inference based on robust (bounded influence) versions of these tests remains reliable when the sample does not entirely conform to the model assumptions. The use of these procedures is illustrated with data coming from a recent randomized controlled trial, with a sample size of 52 observations. An R package implementing all tests is readily available.