When you get a virgin ATTiny, you need to set the fuse bits on it. It does not require the Arduino bootloader, but the process is similar to burning the bootloader. This tutorial helped me get my ATTiny85 up and running, take note of the "Configuring the ATtiny to run at 8 MHz (for SoftwareSerial support)" section.
Also, I've noticed there are different 'board drivers': the items that appear in 'Tools > Board' in the Arduino IDE. You may be using a set that does not work, try this, this or have a google around to find more. Just be sure to go through the entire process when you try a new set (i.e. burn the bootloader, reboot, burn your code).
Good luck.