1-wire in ATMEGA1281 problem
According to the datasheet, if you are powering the temperature sensor from an external supply, that supply must be connected to VDD.  In your case you would wire directly from your 5V supply to pin 3 of each temperature sensor, bypassing the 4.7k resistor.

However, leaving the devices unpowered should not cause random bytes to be received.  There are three possibilities I can think of:


Wrong encoding: Your computer's serial monitor probably expects ASCII characters to be transmitted over the COM port, not raw byte values.  You must convert your numbers to strings before transmitting them.
Bad program: make sure that your device is being programmed correctly by uploading a program that blinks an LED or sends a short string to the COM port repeatedly.  If you are using a library for 1-wire communication, double-check the pin assignment in your program.
Wrong serial settings: if you are, as I assume, using the FTDI device to transmit messages between your computer and microcontroller, make sure that it is connected to the correct pins on your microcontroller and that both are using the same speed and settings.  Most devices operate at a speed of 115200 baud with 8 data bits, 1 stop bit, and no parity.