how is the nai form of a verb related to the verb masu stem
It isn't. The "nai form" of a verb is entirely dependent on the "Mizenkei base", whilst the "masu form" of a verb is entirely dependent on the "Ren'yōkei base". Incidentally, the mizenkei base and the ren'yōkei base have the same pattern for ichidan verbs, but they are unrelated.
how is the nai form of a verb related to … nai/nakatta (from aru)?
If you are new to these "verb bases", you can read up about them on Wikipedia. To summarise, the forms/suffixes of verbs are only compatible with specific verb bases. The negative, passive and causative forms/suffixes are only compatible with the mizenkei base.
Actually, the verb "aru" is an exception that doesn't actually have a mizenkei base, which might explain why the negative form is simply "nai". As for the examples you used, the negative form can be summarized as follows:
||+ Negative Suffix
It's worth noting that since "aru" has no mizenkei base, it cannot be conjugated into the passive or causative forms.