I'm currently using Jenkins with AWS EC2 plugin to run CloudFormation scripts from Jenkins slaves in different AWS accounts. The only way I got this working was by creating dedicated AWS users for Jenkins in the accounts in which I want to launch the slaves. 

The reason I had to do this appears to be that when "Use EC2 instance profile to obtain credentials" is checked, the SSH key is verified against Jenkins master's account, while the SSH-key belongs to the accounts in which I want to launch the slave. 

Solution proposal: Allow the user to enter the AWS Account id in which the slave is to be launched, which would allow Jenkins master's EC2 to assume a role in the proper account in order to verify the SSH key.