Same problem with me. I have had one instance working for over a year and all of a sudden I get the following error when using AusPOST Parcel Post:
ERROR: The delivery rate for this option cannot be determined at this time
If you prefer to use this option as your shipping method, please contact the store owner.
I too believe there must have been a change at Australia Post.



