apt-get purge nova-client
apt-get update && apt-get upgrade

Used this script to re-install nova-agent: https://github.com/rackerlabs/openstack-guest-agents-unix/blob/master/tools/nova-agent-builder.sh

>> extract the tar and ./install.sh

sed '1i### BEGIN INIT INFO\
# Provides: Nova-Agent\
# Required-Start: $remote_fs $syslog\
# Required-Stop: $remote_fs $syslog\
# Default-Start: 2 3 4 5\
# Default-Stop: 0 1 6\
# Short-Description: Start daemon at boot time\
# Description: Enable service provided by daemon.\
### END INIT INFO\
' /usr/share/nova-agent/1.39.1/etc/generic/nova-agent > /usr/share/nova-agent/1.39.1/etc/generic/nova-agent.lsb

cp /usr/share/nova-agent/1.39.1/etc/generic/nova-agent.lsb /etc/init.d/nova-agent

chmod +x /etc/init.d/nova-agent

service xe-linux-distribution stop
service xe-linux-distribution start
service nova-agent start

# ps aux | grep nova
root      7874  0.0  0.7 143984  7464 ?        Ssl  09:02   0:00 /usr/sbin/nova-agent -q -p /var/run/nova-agent.pid -o /var/log/nova-agent.log -l debug /usr/share/nova-agent/nova-agent.py
root      7890  0.0  0.0  11980   928 pts/0    S+   09:03   0:00 grep --color=auto nova

Sources:
http://www.syntheticworks.com/rackspace-cloud/linux-rackspace-cloud/all-about-nova-agent-linux/
https://github.com/rackerlabs/openstack-guest-agents-unix/blob/master/tools/nova-agent-builder.sh
http://bootrackspacecom.readthedocs.org/en/latest/nova_agent/