We study the propagation dynamics of bright optical vortex solitons in nematic liquid crystals with a nonlocal reorientational nonlinear response. We investigate the role of optical birefringence on the stability of these solitons. In agreement with recent experimental observations, we show that the birefringence-induced astigmatism can eventually destabilize these vortex solitons. However, for low and moderate birefringence, vortex solitons can propagate stably over experimentally relevant distances.