Android documentation is something to be desired ;).

Given the following tutorial on creating Custom Toast Notifications.
Toast Notifications

They neglect to say how to do it from a service!

LayoutInflater inflater = ( LayoutInflater ) getSystemService( LAYOUT_INFLATER_SERVICE );
View layout = inflater.inflate( R.layout.toastview , null );

ImageView image = ( ImageView ) layout.findViewById( R.id.image );
image.setImageResource( R.drawable.meteor );
TextView text = ( TextView ) layout.findViewById( R.id.text );
text.setText( this.client.getLastError() );

Toast toast = new Toast( getApplicationContext() );
toast.setGravity( Gravity.CENTER_VERTICAL , 0 , 0 );
toast.setDuration( Toast.LENGTH_LONG );
toast.setView( layout );
toast.show();