The sender has probably encrypted the email with your old key. Advice them to clear their key cache.
On Android or Secure Phone device, they should
1. Open the app drawer and select Key management.
2. Tap Manage public keys and select the Cached tab.
3. Select your account from the list.
4. On the following screen, tap Delete Key.
This will delete the cached key from their app, and your new key will be downloaded automatically from the server.