Sometimes the seal is not actually all way in the housing. It normally moves the last little bit when you lock the handle in but it sounds like you still have a gap. Can you tell whether the leak is from the seal->basket side or the seal->head side? If it is the basket you should see some coffee slurry on the rim of the basket and seal.
The seal should feel firm but flexible so if it is otherwise then it may be suss. Where did you get the seals from?
If you had trouble getting the seal out in the first place you may have damaged the face inside the head such as gouging. Have you had a look with a torch?