Try to turn off bluetooth, in my case Arduino runs very slow when I have bluetooth SPP com ports active

I don't know I'm typing commands old style, I'm using PuTTY even on my Windows mobile phone

I'm glad it worked . To be honest for the purpose of changing baud rates and other AT commands I use PuTTY, because Arduino serial monitor doesn't work for me, so I reccomend you PuTTY, it's free, crossplatform and awesome

If you want to change baud rate on your bluetooth module you need to bring it to AT mode (there should be a switch or you need to pull some pin down check some datasheets) and then you need to connect it to the PC via FTDI and chanage it with AT commands.

What baud rate you have on your BT module ? because it has to be the same that the rate of which you're uploading with in this case 57600, and have you tried to reset the board manually just after you send that avrdude command ? Remember there is no autoreset feature when dealing with BT. I was programming my arduino via bluetooth on the windows 7, there were some issues with the timing of that reset. Haven't tried it on ubuntu yet, but I will look into it

I assume that Optiboot Bootloader requires 16mhz oscillator to run, what error did you get after trying to burn the Bootloader ?

Have you bought that ATmega328 alone ? It's blank or it has some Bootloader in ? One way or another I believe that even if there is Bootloader on it, it will be one that requires 16 MHZ oscillator. So you need to change fuses on that chip and also burn there a corresponding Bootloader.

Are you running Arduino 1.0 or older one ?
Verbose output could show more
on older Arduino software just hold shift while uploading
and on Arduino 1.0 go to file -> preferences -> show verbose output

Bootloader that you have on chip is for UNO right ? So fuses are set for 16 mhz oscillator you need to change these via AVR dude or via burning a bootloader for arduino that uses internal oscillator

Have you changed the fuses on atmega328 ?

[The FTDI FT232RL chip on the Nano is only powered if the board is being powered over USB]

this is originally written about NANO on this site

Power:
The Arduino Nano can be powered via the Mini-B USB connection, 6-20V unregulated external power supply (pin 30), or 5V regulated external power supply (pin 27). The power source is automatically selected to the highest voltage source.

The FTDI FT232RL chip on the Nano is only powered if the board is being powered over USB. As a result, when running on external (non-USB) power, the 3.3V output (which is supplied by the FTDI chip) is not available and the RX and TX LEDs will flicker if digital pins 0 or 1 are high.

Hi I have two NANOs myself and I'm dealing with same issue. I'm guessing that the problem is in 5V auto selector. In Other arduinos there's some sort of transistor to deal with that. But since NANO is so small thing used to select voltage between USB and Input is Schottky diode.

try this
http://firmata.org/wiki/Main_Page

If you have UNO you can use 10V adapter with barrel jack and you can access this voltage on VIN pin on Arduino

It depends on which Arduino are you using. If you're using UNO, Duemilanove, Nano etc. you can use up to 12Volts on VIN pin