Your difficulty is not with the colon, or rather, if you do the following, the colon will present no difficulty at all: the real difficulty is you cannot simply create the string and see Excel consider it as a reference. You must ALSO use a function, INDRECT(), to tell Excel it is not an ordinary bit of text it has created but rather that it should be considered an address reference.
Use:
=INDIRECT("'All Weeks'!"&E1&B3&":"&E1&C3)
and it will work as expected.
However, once you put it in the MATCH() function, you may get an #N/A! error. This is because your formula does not select a match type (third parameter, optional, after the range). So Excel assumes you want a match that is less than the lookup value. If you have no cells in the range with a negative number, you will get the error. Besides that, since you want an exact match, you need to specify so in order that you know you are getting one when it gives a result: the result is the place in the list which will build the cell address you desire from and NOT the actual value being looked up so you probably would not notice any matches you would consider wrong, not at first glance anyway.
So include the third parameter:
=MATCH(0,INDIRECT("'All Weeks'!"&E1&B3&":"&E1&C3),0)
to make it sing.
(Since you want to find the cell, lock it down, the usual "better" ways of doing this lookup do not apply as they would tell you it exists, not where it is.)
So that's the idea. The colon is only a problem because the approach needs one more element, not because of any intrinsic fact about the colon itself. And add the third parameter to ensure you get the right answers.