since it's just this one server,
could it be something like database mail is not emabled, even though you've created the profile?
it sounds like maybe you scripted the database mail settings out and ran them, but not the configure?
http://msdn.microsoft.com/en-us/library/ms191189.aspx
use master
go
sp_configure 'show advanced options',1
go
reconfigure with override
go
sp_configure 'Database Mail XPs',1
go
sp_configure 'SQL Mail XPs',0
go
reconfigure
go
Lowell