Question Regarding EC2 Email Sending Restrictions

I requested the removal of EC2 instance email sending restrictions in a specific region (eu-west-2). My request was approved last week, however my instance in that region is still unable to make an outbound connection to any other mail server's port 25 - all attempts timeout. I've tried sending mail through postfix, and also just connecting to another host I control using telnet. I could connect to e.g. port 80 but not port 25 from the AWS instance whereas both worked locally.

The instance in question has an elastic IP, and the elastic IP has an appropriate rDNS record setup. The security group permits outbound connections on port 25 to any destination.

The instance and elastic IP were created prior to the restriction being lifted, although I have since created a couple of additional instances with different base AMIs and validated that these too seem to be restricted.

Am I simply being too impatient - there was nothing in the message I received stating there would be any wait and it has now been over 48 hours - or is there some other issue at play here?