I believe your "must issue a starttls command first" error message is coming from the mail server which you are transmitting your e-mail to. It may be set up to only accept encrypted connections for message transmissions. You could verify this by trying to telnet into the mail server and mimicking the SMTP protocol exchange which might look somewhat like this:
putty -telnet mail.example.com 25
> 220 mail.example.com Microsoft ESMTP MAIL Service ready at Wed, 29 Jun 2011 11:57:31 +0200
< helo test
> 500 5.3.3 Unrecognized command
< helo test
> 250 mail.example.com Hello [126.96.36.199]
< mail from:<firstname.lastname@example.org>
> 250 2.1.0 Sender OK
< rcpt to:<email@example.com>
> 250 2.1.5 Recipient OK
> 354 Start mail input; end with <CRLF>.<CRLF>
In this example, lines beginning with ">" are mail server replies and lines beginning with "<" are what you need to type to get the replies. Replace mail.example.com with the mail server you are using. If you will see "must issue starttls first" anywhere in the exchange, then this is it.
If you are using the Database Mail configuration wizard of SQL Server 2008 to define your mail server account settings along with the sp_send_dbmail stored procedure to send the mail, you simply will need to make sure that the "this server requires a secure connection (SSL)" checkbox is checked in the account's properties.