If I lost/have no access to the private key associated with a distribution certificate:
Can I just create a new one?
If I do, will it produce any problems during the submission process?
Will apps signed with the old certificate stop working?
Will I be able to update apps signed with the old certificate?
You can request a new Distribution Certificate on the iPhone Developer Program Portal and then create a new Provisioning Profile for App Store distribution.
This should not create any problems for the distribution process.
Apps uploaded with the old certificate will continue to work and you will be able to release updates for existing apps.