Amaury, I can't reproduce the issue you're seeing with empty dicts.
Here's what I'm doing:

dhcp-172-19-19-199:trunk collinwinter$ ./python.exe 
Python 2.7a0 (trunk:71100M, Apr  3 2009, 14:40:49) 
[GCC 4.0.1 (Apple Inc. build 5490)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import cPickle, pickletools
>>> data = cPickle.dumps({}, protocol=2)
>>> pickletools.dis(data)
    0: \x80 PROTO      2
    2: }    EMPTY_DICT
    3: .    STOP
highest protocol among opcodes = 2
>>> data
'\x80\x02}.'
>>>

What are you doing to produce the MARK SETITEMS sequence?