Affine plaintext attack with GCD != 1
You seem to have made a mistake in your arithmetic: $$108108 - 72097 = 36011 \ne 36012.$$

The number $36011$ is invertible modulo $256256$, and thus you can find $a$ and $b$ in a straightforward manner.

More generally, you could end up in a situation where both the difference of the ciphertexts $d_c$ and the difference of the plaintexts $d_p$ might share the same common factor $g$ with the modulus $m$.  In that case, what you can do is divide both of the differences and the modulus by this common factor to obtain $d'_c = d_c / g$, $d'_p = d_p / g$ and $m' = m / g$, and solve the reduced recurrence $d'_c \equiv a d'_p \pmod{m'}$.  This will give you the value of $a$ modulo $m'$, which will correspond to $g$ different possible values of $a$ modulo $m$, differing by multiples of $m'$.  If $g$ is relatively small, this can be almost as good for most purposes as obtaining a unique solution, since e.g. to decrypt any additional ciphertext you can just try all the possible solutions and see which of the results makes the most sense.