Australia Post shipping not working...

I want to use shippping FOR and ONLY Australia but when I make a purchase, the shopping cart gives me a 'No shipping method found' error. I configured everything:

I have enabled Manual shipping and Australia Post shipping
Item has weight
Shipping is included at Configuration>Checkout>Workflow
Australia Post shipping Settings
Zone: 13 Australia
Tax Category: None
Minimum price: 0 AUD
Post code: 4020
Additional Fee: 0
Shipping services: Express/Standard/By Air/By sea
reverse order: no
Group products: yes

I also set up paypal:
Zone: 13
Shipping method: Australia post by sea/air/express/standard
Currency: AUD
percentage: 0%
URL: I won'tput it here but it's set
Email: I won'tput it here but it's set
Address override: yes
NO shipping: no
allow payment notifications: yes
send details: no
enable validation: no
debug: no
etcetera

I'm using kg as weight unit and AUD as the only currency.

Thanks in advance.

Hello,
can you test it without any zone restriction ?

Thank you!

I disabled zone for shipping and payment and it works!

I want to limit purchases to Australia only so I enabled zone for Paypal only and now it offers shipping but no payment for offshore users. I think it's good enough but if you could figure out how to limit both, that would be nice.

Cheers,