Your usage doesn't seem to be wrong. It's just that relatedly isn't an often used word. I think people would be more likely to use "similarly", like some of your comments say. I'd also use:
- "On a related note,"
- "In the same vein,"
To name a few, anyway, it seems like most of your comments have covered what words would be better used instead of "relatedly".
I wasn't sure if the usage of relatedly could be considered standard... I've heard it used before, but just in books. I wasn't sure if people said it very often, though. So, I figured I'd use the British National Corpus (BNC) and the Corpus of Contemporary American English (CCAE) to see how much "relatedly" is used and in what context. Just so you know, a corpus is just a large collection of texts. I don't know how often they're used for requests like these, but one of the other questions I answered here was looking for some way to find word frequencies and corpora (corpuses?) happened to turn up in many of the sources I stumbled upon while I was looking for an answer to that question.
I actually don't know much about the BNC's sources, just that 90% of it is written word and 10% spoken word, so I don't think it's helpful for your purposes. I think this is the best corpus I can use for British English though... and I wanted something with British English just in case you're not in America where the usage frequency could be (and probably is) different. The CCAE uses examples from spoken word (from TV and radio stations like Fox and National Public Radio), fiction publications, and non-fiction publications (magazines, newspapers, and academic publications mostly, though). I'm sure if someone knows a better place to look for word frequencies in British English, they'll tell you, though.
What I got for relatedly were 6 uses in the BNC, none of which were spoken word. There were 64 hits in the CCAE, which had almost all of them in academic publications and non-fiction magazines (Mechanical Engineering, School Psychology Review, and so on) and there were no results for spoken word. Comparatively, the use of the word similarly got 4459 results in the BNC and 13865 in the CCAE (and there was at least one use in every type of source: spoken word, fiction, academic, magazines, and newspapers).
Based on that "research" it seems to me that the usage of relatedly might sound strange because it's not a very common spoken word and it's almost always used in an academic sense. So it would come across odd if you used it in everyday language and that's probably why it sounds strange to your ears as well.