What does it mean when someone says he has an agenda? Is there a negative connotation to agenda? If there is, then why and what is a word that means the same thing but has a positive connotation?
Yes, in this use it has a negative connotation. This use may have come from the longer expression "hidden agenda" (which effectively means "hidden purpose", "hidden thought behind doing something").
If you want a more positive connotation, then you could simply say: "He has a plan", "He has a proposal"...
I came in with the express purpose of checking out whether to have an agenda has a negative connotation or not – as such it was in the back of my mind. The fact that there is a relevant discussion here means that this idiom has in fact developed towards this connotation. As far as I'm concerned, the answer is: yes, it can have an inherent negative meaning: "John came all the way from California to see Mr. Psmith. And he had an agenda".
I'd add my viewpoint as follows:
When a person "has an agenda", I perceive it mostly as negative, whether its intent is meant to be against something positive or not. This is because it is the agenda of one individual. Individual agendas also rarely adapt, so if evidence started saying it needed to, it would mostly not. The connotation is usually about hidden agendas (i.e. he has an agenda, but it hasn't been revealed.)
When an organization "has an agenda", I perceive it mostly negative, but not as much so. If the agenda is revealed, then it is neutral to positive. Mostly when this statement is made, it is for a hidden agenda. Organizations though are more likely to adapt their agendas.
If it is an event that "has an agenda", I think the connotation is entirely positive. the conference or meeting "has an agenda". Whether you know it or not, is less important now, because the one thing you know you need for events is structure.