I have exactly the same problem.
Running on Windows 7 Pro SP1
Using gvim 7.3.46

Part of my _vimrc::

setglobal fileencoding=utf-8
"------------------------------------------------------------------------------
" Vundle - plugin management
"------------------------------------------------------------------------------
set nocompatible               " be iMproved
filetype off                   " required!

set rtp+=~/.vim/bundle/vundle/
call vundle#rc()

" let Vundle manage Vundle
" required! 
Bundle 'gmarik/vundle'

" My Bundles here:
"
" original repos on github
Bundle 'UltiSnips'
Bundle 'mattn/calendar-vim'
Bundle 'rosenfeld/conque-term'
Bundle 'The-NERD-Commenter'
Bundle 'vimwiki'
Bundle 'surround.vim'
Bundle 'brymck/nekotako'
Bundle 'VST'
Bundle 'vcscommand.vim'
Bundle 'Solarized'
Bundle 'taglist.vim'
Bundle 'Python-mode-klen'
Bundle 'unimpaired.vim'
Bundle 'ctrlp.vim'

filetype plugin indent on     " required!
"
" Brief help
" :BundleList          - list configured bundles
" :BundleInstall(!)    - install(update) bundles
" :BundleSearch(!) foo - search(or refresh cache first) for foo
" :BundleClean(!)      - confirm(or auto-approve) removal of unused bundles
"
" see :h vundle for more details or wiki for FAQ
" NOTE: comments after Bundle command are not allowed..

"------------------------------------------------------------------------------
" General
"------------------------------------------------------------------------------
source $VIMRUNTIME/mswin.vim   " Some basic MS keybindings
filetype plugin on             " Enable filetype plugin
filetype indent on             " Enable indent pluing

===end of _vimrc snippet ====================
When trying to use any of snippets (like "def" in python file), it prints out:

===start error printout===
An error occured. This is either a bug in UltiSnips or a bug in a
snippet definition. If you think this is a bug, please report it to
https://bugs.launchpad.net/ultisnips/+filebug.

Following is the full stack trace:
Traceback (most recent call last):
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\__init__.py", line 23, in wrapper
    return f(self, *args, **kwds)
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\__init__.py", line 536, in expand
    if not self._try_expand():
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\__init__.py", line 866, in _try_expand
    self._do_snippet(snippet, before, after)
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\__init__.py", line 848, in _do_snippet
    self._jump()
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\__init__.py", line 731, in _jump
    _vim.select(self._ctab.start, self._ctab.end)
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\_vim.py", line 119, in select
    _unmap_select_mode_mapping()
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\_vim.py", line 207, in _unmap_select_mode_mapping
    all_maps = list(filter(len, eval(r"_tmp_smaps").splitlines()))
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\_vim.py", line 101, in eval
    return as_unicode(rv)
  File "C:\Users\jan.vlcinsky\.vim\bundle\UltiSnips\plugin\UltiSnips\compatibility.py", line 69, in as_unicode
    return s.decode("utf-8")
  File "C:\Python27\Lib\encodings\utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
UnicodeDecodeError: 'utf8' codec can't decode byte 0xa0 in position 4875: invalid start byte
===end of error printout

I wiped out few times the dir of UltiSnips and reinstalled, but with no change.

If I commented out loading mswin.vim and placed the Bundle UtliSnips to the top of loaded bundles, it worked, but

1) living without mswin.vim is not so easy
2) anyway, I got some other problems anyway

Conclusion
=========
I do not consider this issue to be invalid.

The features offered by UltiSnips are realy nice (and I like Python), but till it is not reliable, I do not dare to use it daily. I guess, there is some general issue with character encoding (what is never easy stuff in Python 2.x)