Controlling Arduino with Standard Cell Phone

Is controlling a Bluetooth Arduino or an Arduino with a Bluetooth module possible using a simple Bluetooth cell phone possible or would you need a smartphone/pocket pc?

Controlling it in what way? The Arduino with Bluetooth uses the bluetooth as a serial port. If you can send and receive serial data on your phone, you could develop a protocol for controlling the Arduino.