You need to sign up for the Product Advertising API and create your Access Key ID and Secret Access Key ID credentials on this page within your Amazon Associates account:
If this URL isn't working, please follow these steps:
Log into Amazon Associates > Look in the navigation menu for "Tools" and click that > Click "Product Advertising API" from the drop down.
When you're on the Product Advertising API page, you can scroll down and there should be an option to either migrate your keys (if you created them before) or create new keys.
Use the keys you create on that page within the EasyAzon plugin settings area on the "Credentials" tab inside your WordPress blog. Once you enter your credentials you should be able to do product searches.
If you can't perform product searches:
If you go to this URL and click "SearchItems" on the left-hand side menu:
You can enter your Secret Access Key ID and Access Key ID along with your Amazon associates ID and do a search. Amazon will report back a more detailed answer as to what the issue is.
If the error is related to too many requests, then you're likely not driving enough revenue as an Amazon affiliate yet to use the Product Advertising API.
See this help doc which outlines the usage: