It might take a while for the old reverse record (PTR) to leave the caches of the servers out there, so that probably won't show up immediately. When I checked the IP (you didn't mask it properly in the mail headers, so I managed to find it out), it wasn't set on their servers yet. Your IP provider (Vodafone) appears to have the expiry set to 24 hours, so it can take that long to spread once they make the change.
Your IP is also on the SpamHaus PBL list. This list is created from records by ISPs of IPs that should not be sending mail directly (usually residential internet connections). Being on this list will cause problems in sending. If you are on a static IP, your host should file for an exception with SpamHaus.
For other lists, check your IP over at
http://openrbl.org/ (won't work in IE last I checked) and see the details for any lists you show up on. You only need to worry about the positive blacklist items.