I understand that the vega of the Black-Scholes equation is a positive function, which means the value of the option is an INCREASING function of the volatility, since vega is the derivative of the value with respect to the volatility $\sigma$.
On the other hand it is also true that for an at-the-money call option, the probability of exercise is a DECREASING function of $\sigma$ since so is N(d2).
My question is: how can these two statements be true at the same time?
This is a very astute observation and good question which reveals a seemingly paradoxical (and commonly known) aspect of the Black-Scholes model.
In the Black-Scholes model, the underlying asset price $S_t$ follows a geometric Brownian motion. Under the risk-neutral probability measure, we have at the time of option expiration, $T$, (where the dividend yield is WLOG assumed to be $0$)
$$S_T = S_0e^{(r- \frac{\sigma^2}{2})T}e^{\sigma\sqrt{T}\xi},$$
where $r$ is the risk-free rate, $\sigma$ is the volatility, and $\xi \sim N(0,1)$ is a standard normal random variable. Thus, $S_T$ has a lognormal distribution.
For a given strike price $K$, the risk-neutral probability that a call option expires in the money is
$$P(S_T > K) = P(\log S_T > \log K) = P(\xi > -d_2), \\ d_2 = \frac{\log \frac{S_0e^{rT}}{K}}{\sigma \sqrt{T}} - \frac{1}{2}\sigma\sqrt{T}$$
By the symmetry of the normal distribution, we have $P(\xi > -d_2) = P(\xi < d_2) = N(d_2)$. Now $d_2$ is decreasing for an at-the-money-forward option with respect to $\sigma$. It is also eventually decreasing for any strike price. This confirms that the probability of exercise for a call option is $N(d_2)$ and is or eventually is decreasing with respect to volatility.
On the other hand, you are correct that vega is always positive and, therefore, the value of an option (call or put) must increase as the volatility is increased. This corresponds to the fact that the expected value of the payoff $\mathbb{E}(\max(S_T-K,0))$ increases as $\sigma$ is increased for a lognormal distribution.
It would appear that we have a paradox, but the two facts are not inconsistent.
When the underlying price $S_T$ has a lognormal distribution, it is a nonnegative random variable, i.e. $P(S_T > 0) = 1$. As the volatility increases, the dispersion of the distribution increases and more probability mass accumulates in the finite interval $[0,K]$ than in the unbounded interval $[K,\infty)$.
Now the Black-Scholes value of the call option without discounting is
$$e^{rT}V = S_0 N(d_2 + \sigma\sqrt{T}) - K N(d_2)$$
If the option expires in the money, then the holder in effect pays the strike price and takes delivery of the underlying asset. The strike price is fixed, but conditional on exercise the underlying asset that is delivered has unlimited upside potential. The second term is simply the expected value of the payment. Since this is $0$ if $S_T \leqslant K$ and a constant $-K$ if $S_T > K$, this takes the form $-KN(d_2)$ and this will move closer to $0$ with increasing volatility since it is more likely it will not be realized. On the other hand, the first term always has a positive value and can be explained as
$$S_0N(d_2 + \sigma\sqrt{T}) = S_0\frac{N(d_2 + \sigma\sqrt{T})}{N(d_2)} N(d_2) \\ = \mathbb{E}\left[S_T |S_T> K \right]P(S_T > K).$$
This term increases with $\sigma$ because even though the probability of exercise decreases, the conditional expectation of the underlying asset price (with unlimited upside) increases at faster rate. The net effect of the behavior of both terms is, of course, that the value of the call option increases as the volatility is increased.