On Mac OS X 10.5

$ LC_ALL=ru_RU.koi8-r python3.0 -c 'import time;print( time.strftime("%A"))'
Traceback (most recent call last):
  File "<string>", line 1, in <module>
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 0-1:
invalid data

See http://bugs.python.org/issue5398

Here the issue might be different though. Does 
$ LC_ALL=ru_RU.koi8-r python3.0 -c 'import time;time.strftime("%A")'
(without the print) work?

I don't have the ru_RU locale but here time.strftime() return 'str', not
'bytes' and the utf-8 codec should be able to encode it:
>>> time.strftime("%A")
'Saturday'
>>> type(_)
<class 'str'>

I was able to reproduce this using an italian locale on Windows:
>>> locale.setlocale(locale.LC_TIME, 'Italian_Italy.1252')
'Italian_Italy.1252'
>>> time.strftime("%A", time.strptime("2009-05-01", "%Y-%m-%d"))
'venerd?'

That should be 'venerdì'.
I also found http://bugs.python.org/issue3061 and
http://bugs.python.org/issue836035 that seem to be related. (#5398
instead doesn't seem to be related.)

Apparently on Py3.x a unicode string ('str') is returned, whereas Py2.x
returns an encoded string:
>>> time.strftime("%A", time.strptime("2009-05-01", "%Y-%m-%d"))
'venerd\xec'

Same thing here (Linux) with a non-utf8 locale:

>>> locale.setlocale(locale.LC_TIME, "fr_FR.UTF-8")
'fr_FR.UTF-8'
>>> time.strftime("%B", time.strptime("2009-12-01", "%Y-%m-%d"))
'décembre'
>>> locale.setlocale(locale.LC_TIME, "fr_FR.ISO8859-15")
'fr_FR.ISO8859-15'
>>> time.strftime("%B", time.strptime("2009-12-01", "%Y-%m-%d"))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 461, in
_strptime_time
    return _strptime(data_string, format)[0]
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 307, in _strptime
    _TimeRE_cache = TimeRE()
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 188, in __init__
    self.locale_time = LocaleTime()
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 72, in __init__
    self.__calc_month()
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 98, in
__calc_month
    a_month = [calendar.month_abbr[i].lower() for i in range(13)]
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 98, in <listcomp>
    a_month = [calendar.month_abbr[i].lower() for i in range(13)]
  File "/home/antoine/py3k/__svn__/Lib/calendar.py", line 60, in __getitem__
    return funcs(self.format)
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 1-3:
invalid data

Well, sorry for the message above. There is a problem but it is with
strptime() actually.

>>> time.strptime("2009-12-01", "%Y-%m-%d")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 461, in
_strptime_time
    return _strptime(data_string, format)[0]
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 307, in _strptime
    _TimeRE_cache = TimeRE()
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 188, in __init__
    self.locale_time = LocaleTime()
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 72, in __init__
    self.__calc_month()
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 98, in
__calc_month
    a_month = [calendar.month_abbr[i].lower() for i in range(13)]
  File "/home/antoine/py3k/__svn__/Lib/_strptime.py", line 98, in <listcomp>
    a_month = [calendar.month_abbr[i].lower() for i in range(13)]
  File "/home/antoine/py3k/__svn__/Lib/calendar.py", line 60, in __getitem__
    return funcs(self.format)
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 1-3:
invalid data

Well, it turns out that strftime() is buggy as well:

>>> tp = time.strptime("2009-12-01", "%Y-%m-%d")
>>> locale.setlocale(locale.LC_TIME, "fr_FR.ISO8859-15")
'fr_FR.ISO8859-15'
>>> time.strftime("%B", tp)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 1-3:
invalid data

This is a duplicate of issue 3061.