The Nagios plugin has 3 modes it can run in to get the data from nagios.
Status.dat file direct (local only, Nagios 2.x or 3.x)
status.cgi (remote, uses screen scrape from Nagios web interface, Nagios 2.x)
helper.cgi (most reliable, remote, Nagios 2,x or 3.x, requires additional CGI - this is the way we use)
From your description it sounds like you're using the status.cgi method. This may not work with some Nagios 3.x or if you have in any way customised your status.cgi, or if you use some non-standard authentication method.
If you can, I'd suggest installing the helper.cgi on your Nagios server and using the helper.cgi method (the instructions are in the docs with the plugin)
Now we have Nagios3 at our site I can confirm helper.cgi works with Nagios3; I've not tried the status.cgi method yet but I know Nagios3 has a very different HTML in status.cgi so it may not be working with Nagios 3.
UNIX Systems, ITSS, University of Auckland, NZ
Woe unto them that rise up early in the morning... -- Isaiah 5:11