A key-generator outputs an encrypted string that only changes the second half - what weaknesses could that expose? The company I work for provides a software solution. The software is licensed and I have access to the license generator.

We have a company culture of challenging our perceived security but I am a very basic cryptanalyst. I would like to ask for some leads to see if I can prove our license generator needs to be fixed.

Example (not real licenses):


License #1: abc111
License #2: abc222


Real licenses are about 600 chars and look very much like an ssh-rsa public key. 
(I can't explain it, they just look like one! If I could show you a real one, I am sure you would agree there is something in common)
The reason what you called "real licenses" look like ssh-rsa keys is probably just the encoding format for some of them. ssh-rsa keys are base64 encoded, and that might be the only reason. The decode content can really differ based on the license checking algorithm.

You'd probably be better off disclosing your license verification algorithm, and letting people comment on its security/strength which will enable you to improve it in case any issues are found. The fact that the licenses start with the same prefix, on its own, doesn't indicate much about the security of your license verification.
You should also be clear about the assumptions you're making about a potential cracker, and what can they do. That would help assess whether the licensing scheme is secure under those assumptions.