tholder In order to be able to help we would need more information like:
1) what is the name of the exchange?
2) how did you "generate" your "new wallet"? Did you used one of the existing wallets (like Stargazer or the very simple stellar account viewer etc.) or you generated the keys yourself with stellar laboratory or one of the development libraries etc.?
3) what was the error message that you received from the exchange?
Exchanges normally have a minimal amount that you can withdraw (the ones that I know are quite clear about this limit). Also, some exchanges requires that they know enough information about you to withdraw.
On Stellar, there is a minimal amount that you have to keep on your account (which is 2 XLM at the moment). Also, creating a new account on the Stellar, requires a different operation (Create Account) rather than just sending XLM to it.