python dict KeyError for unicode strings only when large number of keys stored

Question

I have an OrderedDict with 3000+ entries. In the sample program with 3 entries when I store keys in Unicode format I am able to do a lookup without any issues for any key. However in the OrderedDict with 3000+ unique key entries I get an error for the entry "Ha Nội" while doing a lookup. The error I get is KeyError: 'Ha N\xc3\xa1\xc2\xbb\x99i'. Giving example code here which works fine. Why this difference?

> recs = ( ("Sant Julià de Loria", "X"), ("Ha Nội", "Y") )
> 
> OrdD = OrderedDict(recs)  
  HVal = OrdD["Ha Nội"] 
  print(HVal)

I am using Python 3.4.3.