It's been two weeks now that I can't brew upgrade my packages on my Macbook Air with OS X Yosemite installed.

I've tried various solutions but nothing worked out...

The strange thing is that all the other commands work perfectly!

# ladislas @LadBookAir.local in ~
→ brew update
Already up-to-date.

# ladislas @LadBookAir.local in ~
→ brew doctor
Your system is ready to brew.

# ladislas @LadBookAir.local in ~
→ brew upgrade
Error: invalid byte sequence in UTF-8
Please report this bug:
    http://git.io/brew-troubleshooting
/usr/local/Library/Homebrew/vendor/okjson.rb:265:in `match'
/usr/local/Library/Homebrew/vendor/okjson.rb:265:in `numtok'
/usr/local/Library/Homebrew/vendor/okjson.rb:254:in `tok'
/usr/local/Library/Homebrew/vendor/okjson.rb:214:in `lex'
/usr/local/Library/Homebrew/vendor/okjson.rb:45:in `decode'
/usr/local/Library/Homebrew/utils/json.rb:10:in `load'
/usr/local/Library/Homebrew/tab.rb:34:in `from_file'
/usr/local/Library/Homebrew/tab.rb:43:in `for_keg'
/usr/local/Library/Homebrew/cmd/outdated.rb:28:in `block (2 levels) in outdated_brews'
/usr/local/Library/Homebrew/cmd/outdated.rb:22:in `each'
/usr/local/Library/Homebrew/cmd/outdated.rb:22:in `block in outdated_brews'
/usr/local/Library/Homebrew/cmd/outdated.rb:19:in `map'
/usr/local/Library/Homebrew/cmd/outdated.rb:19:in `outdated_brews'
/usr/local/Library/Homebrew/cmd/upgrade.rb:9:in `upgrade'
/usr/local/Library/brew.rb:135:in `<main>'

Another interestind thing is that if I call brew upgrade <name of formula> it works seemlessly.

I'm going to do a clean install anyway in two weeks, but for those having the same issue who need a workaround, here is a simple solution:

# create an array with all your installed formulae
$ installed_formulae=($(brew list -1))

# try to `brew upgrade` each formula from the array
$ for formula in "${installed_formulae[@]}" ; do brew upgrade $formula ; done

The output will look like that:
Imgur

Hope this helps! :)