Characterizing a magnetic levitiation system
There are a few issues with your implementation.


You need a flyback diode across that coil if you don't want an overheating transistor and massive interference. Your current schematic at least doesn't show one. I'd suggest using a schottky diode, as they are fast and have a low voltage drop.





If you are having trouble getting the magnet stable, keep in mind that it might have nothing to do with your PID gains and everything to do with the update rate of the control loop. When I did my magnetic levitatior, the bare minimum that I got to work was 200 Hz. Especially if you are using floating point math for the PID controller on an AVR, I bet you can't get stable levitation. Do everything with 8-bit and 16-bit integer math instead (known as fixed point), and you'll easily be able to reach cycle times below a millisecond.  
Both the input and output of your PID controller are non-linearly related to what you want to control (you want to sense distance and control upwards force). Instead, the hall effect sensor output is proportional to the multiplicative inverse of distance squared, and the force exerted upon the magnet by the electromagnet is not only proportional to coil current, but also inversely proportional to distance squared.
PID controllers don't like this nonlinearity. You should compensate for the nonlinearities in your control system, so that the controller operates in a linear space. For the input, calculate a linear distance from the hall effect sensor output and feed that to the controller instead of the raw value. For the output, apply less current for a given requested force when the magnet is nearer, so that the attraction is independent of distance.  




There's also better way for eliminating the contribution of the electromagnet from the hall effect sensor output:

Sample the hall effect sensor output synchronously with your PWM output, so that the flux is measured only when the coil current has decayed to zero at the end of each PWM period. Much simpler hardware wise, the only drawback is that you need to program at a lower level, starting the analog-to-digital conversion each cycle in a timer interrupt. Don't low pass filter the ADC input if you do this though.