You might want to use the '-r' option to tell sed to use extended regular expressions. Basic sed regexes are quite limited.
Second, regular expressions work differently in sed than they do in a shell. * doesn't mean anything by itself, it's a modifier for something else. First you tell it what expression you want to match, then optionally, how many of them you want to match. An expression can be a single letter, a set of letters, or something in brackets.
A by itself just matches the letter A, like you'd expect.
[ABC] by itself just matches the letter A, B, or C.
A* tells it to match 0 or more A characters.
[ABC]* tells it to match 0 or more characters among A, B, C.
[A-Z]* tells it to match 0 or more characters among A, B, C, ..., Z.
[^A]* tells it to match 0 or more characters that aren't A.
(ABC)* tells it to match 0 or more repititions of "ABC".
#!/usr/bin/python
string = "some text in front From here in the middle to here at the end"
fromindex = string.index("From here")
toindex = string.index("to here")
tobeReplace = string[ fromindex : toindex + len("to here") ]
string.replace( tobeReplace , "new text")