Ok so I finaly figured it out, so apparently even if SELinux is disabled it still reads the policy rules, so
reading the audit.log I saw the following

type=AVC msg=audit(1144271107.899:2774): avc:  denied  { name_connect } for  pid=31413 comm="httpd"
dest=25 scontext=root:system_r:httpd_t tcontext=system_u:object_r:smtp_port_t tclass=tcp_socket
type=SYSCALL msg=audit(1144271107.899:2774): arch=40000003 syscall=102 success=no exit=-13 a0=3
a1=bf975610 a2=591114 a3=b6895f38 items=0 pid=31413 auid=0 uid=48 gid=48 euid=48 suid=48 fsuid=48
egid=48 sgid=48 fsgid=48 comm="httpd" exe="/usr/sbin/httpd"

So by running the following command

[root]# audit2allow -i /var/log/audit/audit.log -l

This will print out a list of things that were denied, I found that the following was the most relevant one
"allow httpd_t smtp_port_t:tcp_socket name_connect;"

I then downloaded the SELinux source by doing
[root]# yum install selinux-policy-targeted-sources

Then
[root]# vi /etc/selinux/targeted/src/policy/domains/misc/local.te

And added the "allow httpd_t smtp_port_t:tcp_socket name_connect;"
Then you simply reload SELinux 
cd /etc/selinux/targeted/src/policy/
make load

That changed the error to Authentication Error. So Trac really should be more specific about this (like
tell you what fields are required), you DO need the following fields even if they are blank.
Smtp_user = 
Smtp_password = 
And simply leave them blank. 

Another issue was the fact that I only had '127.0.0.1 localhost' in my /etc/hosts file and apparently
Python requires you to have an extra alias, so I added '127.0.0.1	MachineNameHere	localhost'. After
all that email notifications finally work, now I only gotta get my mailserver to stop marking them as spam :).

Anyways thanks a lot everyone.
                                   James

________________________________________
From: James Molina 

John, I followed your suggestion and got 2 different .py scripts for
testing, I ran the following two and they both worked (after a bit of
tweaking to my HOSTS file) but Trac still throws same error. Also I have
SELinux disabled until I figure this issue out, so I do not believe it's
an issue with that. Got any other ideas?

***********************************************************

import smtplib

def prompt(prompt):

    return raw_input(prompt).strip()

fromaddr = prompt("From: ")

toaddrs  = prompt("To: ").split()

print "Enter message, end with ^D (Unix) or ^Z (Windows):"

# Add the From: and To: headers at the start!

msg = ("From: %s\r\nTo: %s\r\n\r\n"

       % (fromaddr, ", ".join(toaddrs)))

while 1:

    try:

        line = raw_input()

    except EOFError:

        break

    if not line:

        break

    msg = msg + line

print "Message length is " + repr(len(msg))

server = smtplib.SMTP('127.0.0.1')

server.set_debuglevel(1)

server.sendmail(fromaddr, toaddrs, msg)

server.quit()

*************************************************************

Also tried the following script

import smtplib

message = 'blah blah blah'

SENDER = 'me at mydomain'

RECIPIENT = 'my email addr here'

server = smtplib.SMTP('localhost')

response = server.sendmail(SENDER, RECIPIENT, message)

server.close()

print str(response)

***************************************************************

I used the user Apache to test (had to modify the passwd file since by
default it has a shell disabled) and they both work fine. 

 
James

James Molina wrote:
> 
>     self.server = smtplib.SMTP(self.smtp_server, self.smtp_port)
>   File "/usr/lib/python2.4/smtplib.py", line 241, in __init__
>     (code, msg) = self.connect(host, port)
>   File "/usr/lib/python2.4/smtplib.py", line 303, in connect
>     raise socket.error, msg
> error: (13, 'Permission denied')

This is a socket error.  It's saying that you aren't allowed to connect 
using the socket.  That means that it's an operating system issue.  I 
would suspect that it's some selinux funness.  Try sending an email as 
the user that trac runs under (probably apache or www-data).  Also, as 
said user, fire up a python shell and import smtplib and use that to 
send a test message.

-John