Problem with Shipping & Payment when Logged in as Guest

I wonder if anyone has experienced this problem. If we change the shipping or payment methods (ie those appearing in section 3 of checkout) such as adding a new payment method, the change only reflects on the checkout page if the customer is logged in.

If the customer does not log in and proceeds as a guest, they find, when they arrive at payment and shipping options that they have not been updated to include new setting or methods. I have made sure that all groups are ticked for all payment and postage options but I suspect a different problem because even when I delete a payment option completely, it still appears under the ‘guest’ checkout (even though it does not appear if the customer logs in).

Any help would be much appreciated as it is driving me(and presumably my customers) mad!!

Somewhere in the configuration you have set the usergroups to not include 'All'. Select 'All' (which means no group) and I think you'll be fine.