You might want to look at git grafts. Some information is available here: http://www.kernel.org/pub/software/scm/git/docs/git-filter-branch.html
basically, what you want to do is to fake an ancestry.
You did an initial commit on both machines -- let's call them 'baseA' and 'baseB'. Then, you created a second commit on top of that on both sides -- 'secondA' and 'secondB'. What you want to do is tell git that 'secondB' does not have 'baseB' as ancestor, but instead has 'baseA' as parent.
You can this by using grafts. For example, put this in your .git/info/grafts file:
secondB baseA
(but then using the real SHA's). Now, if you look in GitX, you will see that the histories are connected. To make the change permanent, you need to run git filter-branch.
Update from the comments
I'm not sure what you did is 'correct', though it will work. If you do what
you did, you will get as history:
BaseA --- SecondA -- .. - .. - Merge
\ BaseB --- SecondB ... - .. /
Which will work (and the merge will succeed without problems). However, what's
a bit nicer is this:
BaseA --- SecondA -- .. - .. - Merge
\ SecondB ... - .. /
which basically drops "BaseA" as commit and sets "BaseA" as the parent for
SecondB. This should be possible using the graft rule I told you.
To demonstrate this, I created a small repository you can download here.
If you look at the history in GitX ("gitx master second_master"), you will
see that the histories are disconnected. If you move the .git/info/_grafts file to .git/info/grafts, you will get the second, nice-looking history.
I also added a .git/info/wrong_grafts file. If you use that one, you will get the history you created.
If you look at the SHA's in the grafts file, you'll see that the _grafts file basically has this:
SecondB BaseA
and the wrong_grafts file has this:
BaseB BaseA