gistfile1.rb

require 'rubygems'
require 'fb_graph'

ACCESS_TOKEN = "..."

begin
  me = FbGraph::User.me(ACCESS_TOKEN)
  album = me.albums.first
  photo = album.photo!(
    :access_token => ACCESS_TOKEN,
    :image => File.new(File.join(File.dirname(__FILE__), 'nov.gif')),
    :message => 'Hello, where is photo?'
  )
  puts photo.inspect
rescue => e
  puts e.body
end

Here's the results...

Pirate Stuff
{"error":{"type":"Exception","message":"(#1) An unknown error occurred"}}

The first line is the name of the album that I'm trying to load the photo into, to make sure the first calls were succeeding.

I'm afraid the error message is not very helpful. I traced through the code earlier, and it was getting a 500 error from the facebook server. I'm on a windows machine. I've tried uploading directly with RestClient with no luck either. I'm starting to suspect a RestClient / Windows issue.

Umm, this error message isn't helpful :(
As you mentioned, rest-client gem seems had an issue.
http://github.com/archiloque/rest-client/issues/issue/17

Can you try to install newest rest-client master branch?
It might solve your problem.
http://gist.github.com/393345