Basis sets - negative contraction coefficients?
Diagonalization of a matrix means to find the eigenvalues of the matrix and put them into a diagonal matrix:

$$\mathbf{S}^\text{diag}=\mathrm{diag}\left( \lambda_1,...,\lambda_n \right)\tag{1}\label{diagmat}$$

for $\lambda_i$ being the eigenvalues of the matrix $\mathbf{S}$.
When we want to find the eigenvalues of the matrix $\mathbf{S}$ we solve an eigenvalue problem:

$$\mathbf{S}\mathbf{c}=\bar{\lambda}\mathbf{c}\tag{2}$$

for $\mathbf{c}$ being a matrix of the eigenvector, and $\bar{\lambda}$ being a vector of the eigenvalues.
This equation can also be written out in sum-form for the $i$the eigenvalue:

$$\sum_kS_{jk}c_{ik}=\lambda_ic_{ij}\tag{3}\label{eigproblem}$$

Now as you have stated we can define our atomic orbitals as a linear combination of primitive basis functions:

$$\chi_i=\sum_k c_{ik}\phi_k\tag{4}\label{AO}$$

This can be used to evaluate the self-overlap of the atomic orbitals:

$$S_{ii}=\int_\Omega\chi_i^*(\bar{r})\chi_i(\bar{r})\mathrm{d}\bar{r}=\int_\Omega\left|\chi_i(\bar{r})\right|^2\mathrm{d}\bar{r}=\left&lt; \chi_i \left| \chi_i\right.\right&gt;\tag{5}\label{selfoverlap}$$

This can now be expanded out using Eq. (\ref{AO}):

$$S_{ii} = \left&lt; \sum_k c_{ik}\phi_k \left| \sum_j c_{ij}\phi_j\right.\right&gt;\tag{5}$$

Now using the definition of the overlap-integral $S_{jk}=\left&lt; \chi_j \left| \chi_k\right.\right&gt;$ the above equation can be formulated as:

$$S_{ii}=\sum_{j,k}c_{ij}^*S_{jk}c_{ik}\tag{6}$$

Now using Eq. (\ref{eigproblem}) this can be expressed as:

$$S_{ii}=\sum_{j,k}c_{ij}^*\lambda_ic_{ij}=\lambda_i\sum_j\left|c_{ij}\right|^2\tag{7}$$

Now since $S_{ii}$ can be seen to be larger than or equal to zero from Eq. (\ref{selfoverlap}) and $\left|c_{ij}\right|^2$ must also be larger than or equal to zero, it follows that the eigenvalues $\lambda_i$ must all also be larger then or equal to zero.
I.e. from Eq. (\ref{diagmat}) the diagonalized overlap matrix cannot have any negative values.