Q: Why am I getting invalid payment method?

There is no reason for them to want the phone (unless you are having a separate problem with the phone) - billing details are linked to your iTunes account, not to the device.

There is only a limit to the number of free iCloud accounts that can be created on a device (which would give an error along the lines of 'The maximum number of free accounts have been activated on this iPhone') - that limit cannot be increased. You are trying the create process from scratch, not just overtyping the email address ? You can also create a new account via http://appleid.apple.com or a computer's iTunes

Anything that you downloaded on your old account are permanently tied to that account, only that account can download updates to them.

What happens when you try to download them, and what have you tried to see if it fixes whatever the problem is ?

Unless you've jailbroken your phone then it hasn't got a virus. If you are still trying to use a prepaid card then you will get an invalid message, it will fail the iTunes validation. If you currently have a card on your account have you tried just logging into the account, not when trying to download something, and seeing if you get the 'none' option so that you can remove it : Change or remove your Apple ID payment information - Apple Support ?

What asks for your other account's password ? If you have apps from your old account still on your phone and they have updates available then you can only use that old account to download those updates - you will have to delete those app and buy/download them on your new account to be able to download future updates to them.