Ubuntu CloudFormation Tools installation snippet. Modified version of http://krunchtime.it/setting-up-bootstrapping-using-cfn-init-for-aws-ubuntu-ec2-instance

ubuntu-cloudformation.json

"UserData": {
  "Fn::Base64": { "Fn::Join":["", [
    "#!/bin/bash -ex\n",
    "apt-get update\n",
    "apt-get -y install python-setuptools\n",
    "mkdir aws-cfn-bootstrap-latest\n",
    "curl https://s3.amazonaws.com/cloudformation-examples/aws-cfn-bootstrap-latest.tar.gz | tar xz -C aws-cfn-bootstrap-latest --strip-components 1\n",
    "easy_install aws-cfn-bootstrap-latest\n",
    "/usr/local/bin/cfn-init --stack ", { "Ref":"AWS::StackName" }, " --resource WebServer", " --region ", { "Ref": "AWS::Region" }, "\n",
    "\n",
    "/usr/local/bin/cfn-signal --exit-code $? '", { "Ref" : "WaitHandle" }, "'\n"
  ]]}
}

It seems like cfn-hup does not send notify signal so the service description by @gregmac would never start successfully. The daemon will run of course but systemd thinks it is not ready and will try to restart it every 2 minutes (TimeoutStartSec). To fix this simply replace the content of /etc/systemd/system/cfn-hup.service as follows:

            #systemd service 
            '/etc/systemd/system/cfn-hup.service': 
              content: |
                [Unit]
                Description=Cloud formation helper daemon

                [Service]
                ExecStart=/usr/local/bin/cfn-hup
                Restart=always
                Type=simple

                [Install]
                WantedBy=multi-user.target

Another one taken from https://commscentral.net/tech/?post=50:

    "AppInstanceConfiguration": {
      "Type": "AWS::AutoScaling::LaunchConfiguration",
      "Metadata": {
        "AWS::CloudFormation::Init" : {
          "config" : {
            "files" : {

              "/etc/cfn/cfn-hup.conf" : {
                "content" : { "Fn::Join" : ["", [
                  "[main]\n",
                  "stack=", { "Ref" : "AWS::StackId" }, "\n",
                  "region=", { "Ref" : "AWS::Region" }, "\n"
                ]]},
                "mode"    : "000400",
                "owner"   : "root",
                "group"   : "root"
              },

              "/etc/cfn/hooks.d/cfn-auto-reloader.conf" : {
                "content": { "Fn::Join" : ["", [
                  "[cfn-auto-reloader-hook]\n",
                  "triggers=post.update\n",
                  "path=Resources.AppInstanceConfiguration.Metadata.AWS::CloudFormation::Init\n",
                  "action=/usr/local/bin/cfn-init -v ",
                  "         --stack ", { "Ref" : "AWS::StackName" },
                  "         --resource AppInstanceConfiguration ",
                  "         --region ", { "Ref" : "AWS::Region" }, "\n",
                  "runas=root\n"
                ]]}
              }
            },

            "services" : {
              "sysvinit" : {
                "cfn-hup" : { "enabled" : "true", "ensureRunning" : "true",
                  "files" : ["/etc/cfn/cfn-hup.conf", "/etc/cfn/hooks.d/cfn-auto-reloader.conf"]}
              }
            }
          }
        }
      },
      "Properties": {
        "ImageId" : { "Fn::FindInMap" : [ "AWSRegionToUbuntuAMI", { "Ref" : "AWS::Region" }, "AMIID" ] },
        "SecurityGroups": [{"Ref": "AppInstanceSecurityGroup" }],
        "InstanceType": {"Ref": "AppInstanceType" },
        "IamInstanceProfile": {"Ref": "AppInstanceEC2InstanceProfile"},
        "KeyName": {"Ref": "SSHKey"},
        "UserData"       : { "Fn::Base64" : { "Fn::Join" : ["", [
          "Content-Type: multipart/mixed; boundary=\"=======6t461261365==\"\n",
          "MIME-Version: 1.0\n",
          "\n",
          "--=======6t461261365==\n",
          "Content-Type: text/x-shellscript; charset=\"us-ascii\"\n",
          "Content-Disposition: attachment; filename=\"cfn-setup.sh\"\n",
          "\n",
          "#!/bin/bash\n",
          "set -o errexit; set -o nounset; set -o pipefail\n",
          "# Install AWS cfn-bootstrap utilities\n",
          "apt-get update\n",
          "apt-get -y install python-pip\n",
          "pip install https://s3.amazonaws.com/cloudformation-examples/aws-cfn-bootstrap-latest.tar.gz\n",
          "cp /usr/local/init/ubuntu/cfn-hup /etc/init.d/cfn-hup \n",
          "chmod +x /etc/init.d/cfn-hup \n",
          "update-rc.d cfn-hup defaults \n ",
          "service cfn-hup start \n",
          
          "/usr/local/bin/cfn-init",
          " --stack ", { "Ref": "AWS::StackName" },
          " --resource AppInstanceConfiguration",
          " --region ", { "Ref": "AWS::Region" }, "\n",

          "/usr/local/bin/cfn-signal -e $? ",
          "         --stack ", { "Ref" : "AWS::StackName" },
          "         --resource AppInstanceAutoScalingGroup",
          "         --region ", { "Ref" : "AWS::Region" }, "\n",
          "\n",
          "--=======6t461261365==--\n"
          ]]}
        }
      }
    },

Works like a charm.

What version of Ubuntu are you using? I tried it using Ubuntu 16.04 & 18.04 but I'm getting this error when I run the command:
$ update-rc.d cfn-hup defaults

Job for cfn-hup.service failed because the control process exited with error code.
See "systemctl status cfn-hup.service" and "journalctl -xe" for details.

$ systemctl status cfn-hup.service

● cfn-hup.service
   Loaded: loaded (/etc/init.d/cfn-hup; generated)
   Active: failed (Result: exit-code) since Wed 2018-09-12 04:53:00 UTC; 14s ago
     Docs: man:systemd-sysv-generator(8)
  Process: 7468 ExecStart=/etc/init.d/cfn-hup start (code=exited, status=1/FAILURE)

Sep 12 04:52:59 ip-172-31-0-64 systemd[1]: Starting cfn-hup.service...
Sep 12 04:53:00 ip-172-31-0-64 systemd[1]: cfn-hup.service: Control process exited, code=exited status=1
Sep 12 04:53:00 ip-172-31-0-64 systemd[1]: cfn-hup.service: Failed with result 'exit-code'.
Sep 12 04:53:00 ip-172-31-0-64 systemd[1]: Failed to start cfn-hup.service.

Got this working on Ubuntu 18. Some small changes. Thanks, everyone here for their notes. They were very helpful in figuring out what was going on. Here's a link. https://gist.github.com/mmasko/66d34b651642525c63cd39251e0c2a8b