The initial question was whether I could run the solenoid at those frequencies - which I then learnt was more of a hardware limitation than anything on the Arduino.
My next (and last question hopefully) is, can I use the solenoid controlling circuit that I found in the Arduino.cc repositories?
(Arduino Playground - HomePage)
Thanks so much for the help guys!