Is COM1 the port you normally use to upload to the Duemilanove? Before you upload the code, look in the IDE menu Tools | Serial Port and see which ports are available/visible.
One thing that might have happened is you shorted something out on the board which might have blown something critical on the board, in which case it's toast. But a short can also trigger the USB fuse which then disables the COM port in Windows (although it may depend on your windows version - I know WIN 7 will do this). If that's the case you have to unplug the port, and if it's on a hub unplug that too. Then plug it back in again.
The amount of time needed for a DS18B20 conversion is dependent upon the resolution of the reading. By default this is 12 bits. If you use 9-bit resolution (half a degree precision) the delay is less than 100ms.
There might be a way to do it but the datasheet does not describe the protocol. It implies that whatever protocol is used is a standard one used by FPGAs when they load their configuration from the EEPROM. You'll have to try to dig up info via google/wikipedia etc.
I don't think that is an I2C EEPROM - the datasheet doesn't mention its I2C address. The datasheet says "In-System Programmable (ISP) via Two-Wire Bus" which isn't the same thing as I2C and it also describes the chips as "Serial Memories Designed to Store Configuration Programs for Field Programmable Gate Arrays" which suggests it is more of a special purpose type of chip rather than a generic I2C EEPROM.
Although ICOM describes their CI-V protocol as being CSMA/CD, there is no carrier. It is basically a collision detection protocol with multiple access so it would be more accurate to describe it as MA/CD.