Aaragorn:
Sounds like your problem is that your people just plain don't like you. When I was learning the game, I usually hovered around a 50% approval rating and got shot down a few times when trying to do things - declare war, getting my Senate re-elected, etc.
The nice thing is, this is easy to fix. Slash your taxes for a turn - the morale boost is immediate. Go ahead and declare war, win the vote, then move your taxes back up.
Remember that this is just a short-term or low-difficulty level fix. On the more difficult levels, a low popularity rating will kill your population growth versus the AI players, and you need to consider other options to boost your income instead of just raising taxes - trade, cash for tech agreements, etc.