Why was primality test thought to be NP?
To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP. 

$\bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.

$\bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.

Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $\log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=\log(p)$ and $\sqrt{p}=\frac{1}{2} \log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $\sqrt{p}$ will be $2^{\frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.



The question "Where exactly does the Primality problem lie" has been answered in the link here